Name: Anonymous 2015-08-18 18:36
I am too stupid to understand this paragraph:
The original question was about if Lambda Calculus and Turing Machine are equivalent.
But how about currying? For that we need the following. Suppose X is a represented set. Given any map f:X×ℕ→ℕ computed by a λ-term t, we need to show that the transposition f̃ :X→(ℕ→ℕ) is also computed by some λ-term s. But consider the example where X is the set o fmaps ℕ→ℕ represented by λ-terms, and f is application. Then f̃ would be a map which acts as identity on ℕ→ℕ, but its realizer is a λ-term that converts λ-terms representing maps ℕ→ℕ to corresponding Gödel codes. Such a λ-term does not exist (for example because it would be discontinuous in a topological semantic model).http://cstheory.stackexchange.com/questions/1117/realizability-theory-difference-in-power-between-lambda-calculus-and-turing-mac
The original question was about if Lambda Calculus and Turing Machine are equivalent.