0

...or did it only became apparent after Church's thesis (which asserted that lambda-definable functions and recursive functions are equivalent) and subsequent Turing's thesis? It is known that Godel was not impressed with lambda calculus, does it mean that he also rejected the idea that general recursive functions are enough to express effective calculability?

Siegmeyer
  • 263
  • 1
    This should be an hsm.se question. – J.G. May 17 '20 at 13:25
  • 1
    I've read (but don't remember where --- it may have been in some reminiscences by Church) that Gödel was not convinced by Church's claim that lambda-definability captures the intuitive notion of computability but was convinced by Turing's analysis. – Andreas Blass May 17 '20 at 16:55
  • @AndreasBlass Yes, I think that should be right. I have read something similar from many places. Another interesting thing is that Stephen Kleene was nevertheless quite convinced beforehand ..... due to lack of diagonalization and implementation of number of complicated functions in λ calculus which Church asked him [I will have to search the source of this one but I have def. read it]. Another thing is the Post's machine model, which is extremely similar to TMs, as evidence of CT. Post didn't mention arithmetization and universality though. Anyway ... off-hand I can't re-call the sources. – SSequence May 17 '20 at 18:47

1 Answers1

0

In his essay, "Computability and Incomputability", Robert Soare quotes Godel:

“[Primitive] recursive functions have the important property that, for each given set of values for the arguments, the value of the function can be computed by a finite procedure.”

With a footnote:

“The converse seems to be true, if, besides recursion according to scheme (V) [primitive recursion], recursions of other forms (e.g., with respect to two variables simultaneously) are admitted. This cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle.”

The quote is from "On undecidable propositions of formal mathematical systems", Notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30 pp.

Siegmeyer
  • 263