[ prog / sol / mona ]

prog


Computability Theory of and with Scheme

1 2021-10-29 18:18

I just came across this MIT OCW listing for a computability theory class from 2003 done in MIT Scheme, including lecture notes, code, and assignments:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-844-computability-theory-of-and-with-scheme-spring-2003/

There are slightly more recent materials (from 2005) at:
https://courses.csail.mit.edu/6.844/spring05-6844/handouts/

Here's the course description:

6.844 is a graduate introduction to programming theory, logic of programming, and computability, with the programming language Scheme used to crystallize computability constructions and as an object of study itself. Topics covered include: programming and computability theory based on a term-rewriting, "substitution" model of computation by Scheme programs with side-effects; computation as algebraic manipulation: Scheme evaluation as algebraic manipulation and term rewriting theory; paradoxes from self-application and introduction to formal programming semantics; undecidability of the Halting Problem for Scheme; properties of recursively enumerable sets, leading to Incompleteness Theorems for Scheme equivalences; logic for program specification and verification; and Hilbert's Tenth Problem.

I'm afraid the subject is as yet over my head, but one day I hope to be able to tackle it. In the meantime, I'll be trying out the linked .edwin config.

7


VIP:

do not edit these