A Log-Sensitive Encoding of Turing Machines in the $\lambda$-Calculus

Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni

This note modifies the reference encoding of Turing machines in the $\lambda$-calculus by Dal Lago and Accattoli, which is tuned for time efficiency, as to accommodate logarithmic space.…