Re:On Two Views of Computation in Computer Science
by catnaroek on Thursday September 01, 2016 @10:09PM
(#12410337)
> Regarding (1), can you give a compelling higher-order example for which Church-Turing fails?
I never said the Church-Turing thesis fails. I only said that it only claims what it claims.
> He asserted that Turing Machines could receive the arguments Gödel encoded but the Lambda Calculus couldn't. I don't see why.
In the lambda calculus, if you have the Gödel number of a Turing machine, you can simulate that Turing machine. But if you have a lambda abstraction, you can't produce the Gödel number of a Turing machine that computes the same (partial) function as the lambda abstraction. The only thing you can do with a lambda abstraction is apply it.
I never said the Church-Turing thesis fails. I only said that it only claims what it claims.
> He asserted that Turing Machines could receive the arguments Gödel encoded but the Lambda Calculus couldn't. I don't see why.
In the lambda calculus, if you have the Gödel number of a Turing machine, you can simulate that Turing machine. But if you have a lambda abstraction, you can't produce the Gödel number of a Turing machine that computes the same (partial) function as the lambda abstraction. The only thing you can do with a lambda abstraction is apply it.