patternModerate
Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
Viewed 0 times
equivalentintoexpressionsalgorithmformachinesturingconvertingtherelambda
Problem
We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure.
But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus expression? Is it impossible to have such algorithm? (meaning does it go down to undecidability or NP-Completeness?)
if not, are there any papers or algorithms for doing so?
But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus expression? Is it impossible to have such algorithm? (meaning does it go down to undecidability or NP-Completeness?)
if not, are there any papers or algorithms for doing so?
Solution
All proofs of the equivalence of these two models of computation are constructive, that is they describe an algorithm for converting a program from one model of computation to the other. However, I caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (Turing, Church, Post, Kleene and their ilk).
Context
StackExchange Computer Science Q#48622, answer score: 12
Revisions (0)
No revisions yet.