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).
The original question was about if Lambda Calculus and Turing Machine are equivalent.
Name:
Anonymous2015-08-18 19:50
I can't explain it because I'm a stupid American. You'll have to wait for a Hindu or a Chinaman to come by and explain all this hard maths stuff for you.
Name:
Anonymous2015-08-18 20:36
I do not think you will benefit in any way from going to the effort of understanding this.
Name:
Anonymous2015-08-18 20:44
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.
ok
But consider the example where X is the set o fmaps ℕ→ℕ represented by λ-terms, and f is application.
Ok, f(g,n) = g(n)
Then f̃ would be a map which acts as identity on ℕ→ℕ,
If you curry f(g), you get g.
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).
The first person explained why (with _particular_ representations chosen) TM can do more than LC for (N->N)->N maps. Then he gave reason why higher-order functions are the opposite, and even higher again the opposite et cetera. Currying decreases the order of a function.
>>12 what does can do more for (N->N)->N maps mean?
Name:
Anonymous2015-08-19 15:25
>>14 This is why I tried to understand the 2nd answer, but category theorists sticks at explaining things using words, maybe that's why they draw those silly diagrams...
Name:
Anonymous2015-08-19 19:21
The TM representation contains more information available for use than the LC one.
Name:
Anonymous2015-08-19 19:26
>>16 The question is: why it's not possible to represent that information with lambda terms? I want to understand why Lambda Calculus is not Turing complete.
Name:
Anonymous2015-08-19 19:29
But it is. It's just a representation problem.
Name:
Anonymous2015-08-19 19:29
But it is. It's just a representation problem.
Name:
Anonymous2015-08-19 19:50
If LC is TC then, by Church-Turing thesis, it should be able to represent anything that a TM can represent. Andrej Bauer said that a "a λ-term that converts λ-terms representing maps ℕ→ℕ to corresponding Gödel codes" doesn't exist, I would like to understand why not.