# Constructing a Turing Machine with Lambda Calculus

I'm interested in the implementation of a Turing Machine (deterministic) in Lambda Calculus. How should I proceed to do this? I am not sure on how to start since I must represent the state and infinite tape somehow.

I hope my question makes sense. Thanks in advance.

• I'd write it in Haskell, then realise that all Haskell data types and functions can be encoded into the lambda calculus. – Dave Clarke Dec 14 '15 at 14:35
• Another hint is that "infinite tape" can be represented as a function from a $\mathbb{N} \to \mathbb{V}$, that is, think of the type as a function which is capable of returning the symbol at any particular location on demand. The initial tape is a constant function and you can "modify" it as appropriate – Daniel Gratzer Dec 14 '15 at 15:38
• Yes, but how would I translate an input string and process it to compute the output using the lambda calculus? That is what's confusing me. – Felipe Sulser Dec 14 '15 at 20:30
• The input string would be a function, and you can turn it into another function which represents the output string. E.g. (using an extended syntax) $\lambda s.\ \lambda n.\ {\sf if}\ n=0\ {\sf then}\ 'a'\ {\sf else}\ s\, (n-1)$ changes a string $s$ into $as$, i.e. it prepends the character "a". You can turn that into actual lambda calculus by using Church encodings for booleans/naturals/etc. – chi Dec 15 '15 at 18:18