Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T23:16:33.079Z Has data issue: false hasContentIssue false
  • English
  • Français

Computability and λ-definability

Published online by Cambridge University Press:  12 March 2014

A. M. Turing
A. M. Turing*
Affiliation:
Princeton University
Get access Rights & Permissions [Opens in a new window]

Extract

Several definitions have been given to express an exact meaning corresponding to the intuitive idea of ‘effective calculability’ as applied for instance to functions of positive integers. The purpose of the present paper is to show that the computable functions introduced by the author are identical with the λ-definable functions of Church and the general recursive functions due to Herbrand and Gödel and developed by Kleene. It is shown that every λ-definable function is computable and that every computable function is general recursive. There is a modified form of λ-definability, known as λ-K-definability, and it turns out to be natural to put the proof that every λ-definable function is computable in the form of a proof that every λ-K-definable function is computable; that every λ-definable function is λ-K-definable is trivial. If these results are taken in conjunction with an already available proof that every general recursive function is λ-definable we shall have the required equivalence of computability with λ-definability and incidentally a new proof of the equivalence of λ-definability and λ-K-definability.

A definition of what is meant by a computable function cannot be given satisfactorily in a short space. I therefore refer the reader to Computable pp. 230–235 and p. 254. The proof that computability implies recursiveness requires no more knowledge of computable functions than the ideas underlying the definition: the technical details are recalled in §5.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 2 , Issue 4 , December 1937 , pp. 153 - 163
Copyright
Copyright © Association for Symbolic Logic 1937

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1 Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser. 2, vol. 42 (1936–1937), pp. 230–265 Google Scholar, quoted here as Computable. A similar definition was given by Post, E. L., Finite combinatory processes—formulation 1, this Journal, vol. 1 (1936), pp. 103–105 Google Scholar.

2 Church, Alonzo, An unsolvable problem of elementary number theory, American journal of mathematics, vol. 58 (1936), pp. 345–363 CrossRefGoogle Scholar, quoted here as Unsolvable.

3 Kleene, S. C., General recursive functions of natural numbers, Mathematische Annalen, vol. 112 (1935–1936), pp. 727–742 CrossRefGoogle Scholar. A definition of general recursiveness is also to be found in Unsolvable pp. 350–351.

4 Kleene, S. C., λ-definability and recursiveness, Duke mathematical journal, vol. 2 (1936), pp. 340–353 CrossRefGoogle Scholar.

5 Heavy type capitals are used to stand for variable or undetermined sequences of symbols. In expressions involving brackets and heavy type letters it is to be understood that the possible substitutions of sequences of symbols for these letters is to be subject to the restriction that the pairing of the explicitly shown brackets is unaltered by the substitution; thus in X[L]Y the number of occurrences of [in L must equal the number of occurrences of].

6 Church, Alonzo and Rosser, J. B., Some properties of conversion, Transactions of the American Mathematical Society, vol. 39 (1936), pp. 472–482 CrossRefGoogle Scholar. The result used here is Theorem 1 Corollary 2 as extended to the modified conversion on p. 482.

7 Computable p. 254.

8 This may be done by defining i(x, y) as follows:

S(x) as usual meaning x+1.

9 Compare the two papers by Kleene already quoted.