Lecture 25

Turing machines main characteristic are a tape, and a transition relation, which we can write out as a finite automatons. What happens, if we drop the tape from the machine? A lot! We obtain a machine that can accept only a certain class of strings, also known as the language of regular expressions.

Reading: Robert Harper. Functional Pearls. Proof-Directed Debugging. Journal of Functional Programming.