Recursion Theory

Lecture Notes in Logic 1

Joseph R. Shoenfield

• Publisher: A K Peters/CRC Press
• Year: 2018
• ISBN:
  9781351419413
• Edition: 1
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

This volume, which ten years ago appeared as the first in the acclaimed series Lecture Notes in Logic, serves as an introduction to recursion theory. The fundamental concept of recursion makes the idea of computability accessible to a mathematical analysis, thus forming one of the pillars on which modern computer science rests. The clarity and focus of this text have established it as a classic instrument for teaching and self-study that prepares its readers for the study of advanced monographs and the current literature on recursion theory.

1. Computability

Recursion theory is, at least in its initial stages, the theory of computability. In particular, the first task of recursion theory is to give a. rigorous mathematical definition of computable.

A computation is a process by which we proceed from some initially given objects by means of a fixed set of rules to obtain some final results. The initially given objects are called inputs; the fixed set of rules is called an algorithm; and the final results are called outputs.

We shall always suppose that there is at most one output; for a computation with k outputs can be thought of as k different computations with one output each. On the other hand, we shall allow any finite number of inputs (including zero).

We shall suppose that each algorithm has a fixed number k of inputs. We do not, ever, require that the algorithm give an output when applied to every k–tuple of inputs. In particular, for some k–tuples of inputs the algorithm may go on computing forever without giving an output.

An algorithm with k inputs computes a function F defined as follows. A k–tuple of inputs x₁,…,x_k. is in the domain of F iff the algorithm has an output when applied to the inputs x₁,…,x_k; in this case, F(x₁,…,x_k) is that output. A function is computable if there is an algorithm which computes it.

As noted, an algorithm is set of rules for proceeding from the inputs to the output. The algorithm must specify precisely and unambiguously what action is to be taken at each step; and this action must be sufficiently mechanical that it can be done by a suitable computer.

It seems very hard to make these ideas precise. We shall therefore proceed in a different way. We shall give a rigorous definition of a class of functions. It will be clear from the definition that every function in the class is computable. After some study of the class, we shall give arguments to show that every computable function is in the class. If we accept these arguments, we have our rigorous definition of computable.

2. Functions and Relations

We must first decide what inputs and outputs to allow. For the moment, we will take our inputs and outputs to be natural numbers, i.e., non-negative integers. We agree that number means natural number unless otherwise indicated. Lower case Latin letters represent numbers.

We now describe the functions to which the notion of computability applies. Let ω be the set of numbers. For each k, ω^k is the set of k–tuples of numbers. Thus ω¹ is ω, and ω⁰ has just one member, the empty tuple. When it is not necessary to specify k, we write $\overrightarrow{x}$ for x₁,…,x_k.

A k–ary function is a mapping of a subset of ω^k into ω. We agree that a function is always a k–ary function for some k. We use capital Latin letters (usually F, G, and H) for functions.

A k–ary function is total if its domain is all of ω^k. A 0–ary total function is clearly determined by its value at the empty tuple. We identify it with this value, so that a 0–ary total function is just a number. A 1–ary total function is called a real. (This terminology comes from set theory, where reals are often identified with real numbers. It will lead to no confusion, since we never deal with real numbers.)

A common type of algorithm has as output a yes or no answer to some question about the inputs. Since we want our outputs to be numbers, we identify the answer yes with the number 0 and the answer no with the number 1. We now describe the objects computed by such algorithms.

A k–ary relation is a subset of ω^k. We use capital Latin letters (generally P, Q, and R) for relations. If R is a relation, we usually write $R\left(\overrightarrow{x}\right)$ for $\overrightarrow{x}$ ∈ R. If R is 2–ary, we may also write x R y for R(x,y).

A 1–ary relation is simply a set of numbers. We understand set to mean set of numbers; we will use the word class for other kinds of sets. We use A and B for sets.

If R is a k–ary relation, the representing function of R, designated by χ_R, is the k–ary total function defined by

$\begin{array}{ll}{\chi }_R\left(\overrightarrow{x}\right)=0\hfill & \text{if }R\left(\overrightarrow{x}\right),\hfill \\ \hfill =1& \text{otherwise}\text{.}\hfill \end{array}$

A relation R is computable if the function χ_R is computable. We adopt the convention that whenever we attribute to a relation some property usually attributed to a function, we are actually attributing that property to the representing function of the relation.

3. The Basic Machine

To define our class of functions, we introduce a computing machine called the basic machine. It is an idealized machine in that it has infinitely much memory and never makes a mistake. Except for these features, it is about as simple as a computing machine can be.

For each number i, the computing machine has a register Ri. At each moment, Ri contains a number; this number (which has nothing to do with the number i) may change as the computation proceeds.

The machine also has a program holder. During a computation, the program holder contains a program, which is a finite sequence of instructions. If N is the number of instructions in the program, the instructions are numbered 0, 1, …, N–1 (in the order in which they appear in the program). The machine also has a counter, which at each moment contains a number.

To use the machine, we insert a program in the program holder; put any desired numbers in the registers; and start the machine. This causes 0 to be inserted in the counter. The machine then begins executing instructions. At each step, the machine executes the instruction in the program whose number is in the counter at the beginning of the step, provided that there is such an instruction. If at any time the number in the counter is larger than any number of an instruction in the program, then the machine halts. If this never happens, the machine goes on executing instructions forever.

The instructions are of three types. The first type has the format INCREASE Ri. When the machine executes this instruction, it increases the number in Ri by 1 and increases the number in the counter by 1. The second type has the format DECREASE Ri, n, where n is the number of an instruction in the program. If the machine executes this instruction when the number in Ri is not 0, it decreases the number in that register by 1 and changes the number in the counter to n. If it executes this instruction when the number in Ri is 0, it increases the number in the counter by 1. The third type has the format GO TO n, where n is the number of an instruction in the program. When the machine executes this instruction, it changes the number in the counter to n. Note that if Ri is not mentioned in an instruction, then the instruction does not change the number in Ri and the number if Ri does not affect the action of the instruction.

This completes the description of the basic machine. Of course, ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• 1. Computability
• 2. Functions and Relations
• 3. The Basic Machine
• 4. Macros
• 5. Closure Properties
• 6. Definitions of Recursive Functions
• 7. Codes
• 8. Indices
• 9. Church’s Thesis
• 10. Word Problems
• 11. Undecidable Theories
• 12. Relative Recursion
• 13. The Arithmetical Hierarchy
• 14. Recursively Enumerable Relations
• 15. Degrees
• 16. Evaluation of Degrees
• 17. Large RE Sets
• 18. Functions of Reals
• 19. The Analytical Hierarchy
• 20. The Projective Hierarchy
• Suggestions for Further Reading
• Index