When formulating general recursive functions, did Godel knew that they correspond to effectively calculable functions?

53 Views Asked by At

...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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.