Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-22T14:33:30.853Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite combinatory processes—formulation1

Published online by Cambridge University Press:  12 March 2014

Emil L. Post
Emil L. Post*
Affiliation:
College of the City of New York
Get access Rights & Permissions [Opens in a new window]

Extract

The present formulation should prove significant in the development of symbolic logic along the lines of Gödel's theorem on the incompleteness of symbolic logics and Church's results concerning absolutely unsolvable problems.

We have in mind a general problem consisting of a class of specific problems. A solution of the general problem will then be one which furnishes an answer to each specific problem.

In the following formulation of such a solution two concepts are involved: that of a symbol space in which the work leading from problem to answer is to be carried out, and a fixed unalterable set of directions which will both direct operations in the symbol space and determine the order in which those directions are to be applied.

In the present formulation the symbol space is to consist of a two way infinite sequence of spaces or boxes, i.e., ordinally similar to the series of integers …, − 3, − 2, − 1, 0, 1, 2, 3, …. The problem solver or worker is to move and work in this symbol space, being capable of being in, and operating in but one box at a time. And apart from the presence of the worker, a box is to admit of but two possible conditions, i.e., being empty or unmarked, and having a single mark in it, say a vertical stroke.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 1 , Issue 3 , September 1936 , pp. 103 - 105
Copyright
Copyright © Association for Symbolic Logic 1936

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

Footnotes

1

Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.

References

2 Church, Alonzo, An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58 (1936), pp. 345–363Google Scholar.

3 Symbol space, and time.

4 As well as otherwise following the directions described below.

5 While our formulation of the set of directions could easily have been so framed that applicability would immediately be assured it seems undesirable to do so for a variety of reasons.

6 The development of formulation 1 tends in its initial stages to be rather tricky. As this is not in keeping with the spirit of such a formulation the definitive form of this formulation may relinquish some of its present simplicity to achieve greater flexibility. Having more than one way of marking a box is one possibility. The desired naturalness of development may perhaps better be achieved by allowing a finite number, perhaps two, of physical objects to serve as pointers, which the worker can identify and move from box to box.

7 The comparison can perhaps most easily be made by defining a 1-function and proving the definition equivalent to that of recursive function. (See Church, loc. cit., p. 350.) A 1-function f(n) in the field of positive integers would be one for which a finite 1-process can be set up which for each positive integer n as problem would yield f(n) as answer, n and f(n) symbolized as above.

8 Cf. Church, loc. cit., pp. 346, 356–358. Actually the work already done by Church and others carries this identification considerably beyond the working hypothesis stage. Hut to mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.