0
$\begingroup$

The lambda caculus equals to Turing Machine,so What is lambda caculus's "fix point combinators" corresponding to Turing Machine?

according to the paper <Primitive Rec, Ackerman's Function, Decidable, Undeciable, and Beyond Exposition by William Gasarch>,Turing Machine can:

The machine acts in discrete steps. At any one step it will read the symbol in the \tape square", see what state it is in, and do one of the following:

write a symbol on the tape square and change state, move the head one symbol to the left and change state, move the head one symbol to the right and change state. so what's the "fix point combinators" corresponding to?I think its 2 and 3:"the head can move left and right",it can "the head can move left and right",so it can loop,and "fix point combinators" support loop too

am I right?Thanks!

$\endgroup$
1
  • $\begingroup$ Hint: think about what fixed-point combinators give you in lambda calculus. Or especially in a programming language like Scheme where you can define it very naturally. $\endgroup$
    – ShyPerson
    May 5, 2023 at 3:32

1 Answer 1

4
$\begingroup$

The lambda calculus is not "equal" to Turing machines. There is a correspondence, but it is not equality, it's one of simulation. You should not expect every aspect of one to have a corresponding counterpart in the other. For instance, it does not make sense to ask "what does the Turing machine head correspond to in lambda calculus?"

Having said that, there is a more high level correspondence. The fixpoint combinator implements general recursion in lambda calculus. In command-based languages the (vague) counter-part is iteration, i.e., while loop. And Turing machines are capable of iterating a sequence of actions. However, the correspondence beteween recursion and iteration goes beyond both Turing machines and lambda calculus, so it's not really an answer specific to your question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.