Re:Harvey Friedman bringing incompleteness and infinity out ...
by eastWestMath on Friday February 24, 2017 @12:24PM
(#13725615)
>The belief that Church defined computation rigorously when he solved the Entschidungsproblem using the lambda calculus rather than just made an imprecise conjecture is a common mistake and historical revisionism.
Ok I'm out, you do you man.
Re:Harvey Friedman bringing incompleteness and infinity out ...
by pron on Friday February 24, 2017 @04:05PM
(#13727891)
You're free to believe what you want, or you can go read the abundant material, starting with Church's paper. If you find a thorough treatment of the concept of computation, you can write a paper about it. Church himself explicitly writes that he's unable to give a precise definition. Church was the first (scooping Turing by a few months) to claim that a certain formalism is what we now call Turing complete, i.e., universal with respect to the "vague intuitive notion" of the algorithm, but he was unable to provide a satisfactory justification for his claim (he made a circular argument and then gave up, writing the sentence I quoted above).
Turing, on the other hand, gives a fundamental treatment of what computation is, independent of any particular formalism (in his review of Turing's paper, Church described it as explaining how to construct "arbitrary" computing systems, and Gödel said, in the quote I've given, that Turing was able to give a general, universal, treatment of what a formal system is).
While I can't argue with your claim that Turing had worked with lambda calculus prior to writing On Computable Numbers when he was 24, I have seen no mention of this, but would be happy to see a reference.
BTW, while the lambda calculus does indeed precede Turing's work, its recognition as a universal expression of what is calculable happened at exactly the same time. But regardless, Church does not define the notion of computation, while Turing does.
But you don't have to take my word for it. You can find such rubbish by Gandi (who called Turing's work a "paradigm of philosophical analysis"), Davis, Gödel and many others: Gödel offered enthusiastic praise when he wrote that Turing offered "the precise and unquestionably adequate definition of the general concept of formal system" (Floyd, https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf)
The belief that Church defined computation rigorously when he solved the Entschidungsproblem using the lambda calculus rather than just made an imprecise conjecture is a common mistake and historical revisionism. If anyone came close to defining computation before Turing, that would have been Brouwer.
Also, I don't know if Turing worked on lambda calculus before he wrote On Computable Numbers. After completing the manuscript, he saw Church's new paper and incorporated it in an appendix. Do you have any reference for that?