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.

  • 3
    $\begingroup$ I'd write it in Haskell, then realise that all Haskell data types and functions can be encoded into the lambda calculus. $\endgroup$ – Dave Clarke Dec 14 '15 at 14:35
  • 2
    $\begingroup$ 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 $\endgroup$ – Daniel Gratzer Dec 14 '15 at 15:38
  • $\begingroup$ 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. $\endgroup$ – Felipe Sulser Dec 14 '15 at 20:30
  • $\begingroup$ 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. $\endgroup$ – chi Dec 15 '15 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.