A Log-Sensitive Encoding of Turing Machines in the λ-Calculus
This note modifies the reference encoding of Turing machines in the λ-calculus by Dal Lago and Accattoli, which is tuned for time efficiency, as to accommodate logarithmic space. There are two main changes: Turing machines now have *two* tapes, an input tape and a work tape, and the input tape is encoded differently, because the reference encoding comes with a linear space overhead for managing tapes, which is excessive for studying logarithmic space.
READ FULL TEXT