Finite combinatory processes—formulation

Abstract

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.