A Log-Sensitive Encoding of Turing Machines in the λ-Calculus

01/29/2023
by   Beniamino Accattoli, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset