Abstract
On Computable Numbers, with an Application to the Entscheidungsproblem
The computable numbers may be described briefly as the real numbers whose expression as a decimal is calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real (or computable) variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique.