News for hackers. Stuff that matters.
Re:On Two Views of Computation in Computer Science by tome on Thursday September 01, 2016 @03:18AM (#12403587)
Regarding (1), can you give a compelling higher-order example for which Church-Turing fails?

On Scott's blog Neel talked about functions '(unit -> bool) -> (unit -> bool) -> bool', but this example seems spurious. He asserted that Turing Machines could receive the arguments Godel encoded but the Lambda Calculus couldn't. I don't see why. If you also let the Lambda Calculus receive its arguments Godel encoded then it can inspect them and perform the same dovetailing that the Turing Machine would.

Do you know of a more compelling example?

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.