Effective enumerations and the universal machine

We will introduce the idea of enumerating all computable partial functions and then defining a universal machine that computes any program description on arbitrary inputs.

Notions

Say a partial function is computable or recursive (same meaning) if it is constant or can be defined from substitution, composition, primitive recursion, or minimization of other computable partial functions.

We will consider only partial functions .

Now we play with the idea of encoding data structures into partial functions. Let . Let be an -ary total function that does the following:

1. Let be a fixed ascending sequence of primes where is the next prime after and .
2. Let .

We want to show sequence coding is computable.

Proof. Define by primitive recursion from and :

An easy induction shows that computes the desired result. We’ll take for granted that is a decidable relation. ⁠ 

Proof. Define by primitive recursion from and .

⁠ 

The whole point of sequence coding is to leverage the unique factorization of primes to encode sequences as single naturals. Now it should be obvious how to define functions to extract the element at index in a sequence, count the length of the sequence, etc. Let be a sequence code. Define the relation for if is a valid sequence code, and the partial function to count the length of the code. Let be the element at index (0-indexed).

To summarize, we are using a URM that has an unlimited supply of natural number registers which can be addressed using -based indexing and supports zero, successor, transfer, and jump instructions. However, no indirect addressing is allowed, i.e. we cannot have a program compute a “variable” and say “access the register .”

A URM is basically an abstract machine that is often easier to analyze than a Turing machine. Keeping with Church-Turing, it is of course equivalent to TMs. We will work with URMs.

Since we have the basic list data structure via sequence coding, we can give a sketch towards how to simulate any URM using only recursive partial functions. The idea is that a URM program is simply a finite, enumerable list of instructions . Each instruction is exactly one of the four aforementioned types alongside the parameters. The zero and successor instructions both take a single parameter, the register index to operate on, while the transfer instruction takes two parameters (copying the value of the first register to the second), and the jump instruction takes two register indices and an instruction index.

We basically just want to encode the registers as a sequence code. Each register holds a natural number, corresponding to the natural number entries of our sequence code. Then, we want to somehow encode each instruction. We can do this by fixing a number for each instruction (e.g. 1 corresponds to zero, 2 corresponds to successor, and so on). Then, an instruction is a sequence code whose first entry is the instruction number and the entries after are its parameters (if any). Now the entire program code might be encoded as where is the encoding of the instruction. That is, every URM program description can be represented as a single natural number . When is a URM program and is the corresponding encoding, we say that is code for , and we write

to mean the -ary partial function computed by the URM coded by , i.e. .

Finally, we want to encode a single snapshot of the URM executing, capturing all its state. For each snapshot, we might store the current instruction (with its parameters) and the current register state in a single sequence code. Then we can represent the full computation trace of a URM by building a list of each of its state snapshots as the machine executes. We can build decidable checks for whether a computation state follows from a previous computation state, and whether a state is an initial or halting state. These checks, when combined, can verify whether a computation trace is accurate.

The general idea is that we can (with a lot of bookkeeping) build up increasingly complex relations that encode the structure of URM computations. The prior section is more just food for thought and a cursory sketch to show how it’s plausible the rest of this article can be rigorously justified.

Let us define the following.

• is a valid program code.
• is an initial state.
• is a halting state.
• The computation follows from in program executed on input .

We take for granted that all of these relations are decidable, noting that our previous sketches are reasonably convincing evidence that they wouldn’t be too hard to define.

The Kleene -predicate

The idea of the Kleene -predicate (which is just a fancy name for a particular relation) is to construct a decidable relation that checks whether a URM program code run on an input is correctly described by a sequence of computation steps stored in a sequence code . A search process can then find this correct computation sequence (if the partial function being computed converges), or otherwise it will never find it (i.e. no terminating computation sequence exists, i.e. the function diverges).

Formally, fix and then

Then define

Then .

Applications

The function in the Kleene -predicate section is closely related to the idea of a universal machine that computes any partial function. We take for granted in this section that a URM can compute any recursive partial function. (It is just a matter of tedious bookkeeping to show that any of the recursive definition schemes can be run on a URM.)

Consider the sequence where

equals the -ary function computed by the program coded in on . Then our work above shows that this sequence contains every URM-computable partial function. Also, the -ary function below,

shows that is uniformly computable. We call this sequence an effective enumeration.

Also, since is in particular computable, has a URM program computing it. Let be the program. Then

In English, this says that computes an -ary partial function which takes in a program code and input and outputs the result of running the code on . That is, can simulate the output of any URM. As any partial recursive function is also URM-computable, we call the universal machine for computable partial functions.