Chapter 5. Computability theory

Computability theory deals with the problem of description and analysis of algorithmically solvable tasks. The first question is if every task has an algorithmic solution. The next is if a task has solution there are more and they are really different. Is it possible that a task has only partial solution? What does it mean?

For the precise examinations we need some definition. One of them is the concept of universal Turing machine and the other - or other two - the concept of recursive and recursively enumerable languages.

5.1. Universal Turing machines and universal language

The computers used in the everyday life are called universal, because of their property that they can solve not only a single task, but - with some limitations - theoretically anything. This ability is because one has the possibility to assign different programs to solve the required problem. One of the starting point of our observations in connection with Turing machines, is the assumption - by the Churc-Turing thesis - that they are suitable to describe any algorithm. Then one may ask if the Turing machine can be regarded as a model for the universal computer. To approach this question, we need some definition.

Definition 5.1.

Let  be an integer. A Turing machine  is called universal 
to the -tape Turing machines, if for all  Turing machines  of 
 tapes there exists a word  such that  
 . 
Here  is a separation symbol.

The Turing machine defined above are expected to be able to simulate any Turing machine with a given number of tapes with the help of a proper extension word. Following the analogy with computers, the word can be regarded as the program of . For simplicity, we will call it actually a program.

The first question related to the definition, whether there exist at all such a Turing machine for a given or not. The answer is the following.

Theorem 5.2.

For all  integers there exists universal Turing machine to
the -tape Turing machines.

Proof

The proof is constructive.

Let be fixed. Similarly to the proof of the simulation theorem, the precise proof would require the observation of a lot of technical detail, so we will give a rough proof again.

During the construction we describe a Turing machine which is able to store the program and actual configuration of the Turing machine we are simulating. For this, the universal Turing machine will have tapes. The first tapes are used to store the tape content of the simulated Turing machine. The tape stores the program and tape stores the actual state of the simulated Turing machine.

Furthermore, for simplicity, assume that the tape alphabet of the simulated Turing machine is fixed. This is not a real restriction, since every alphabet can be mapped to the alphabet, such that the symbols are represented by equal length, but different sequences. With such a uniquely decidable encoding the words and languages (tasks) can be mapped between the two alphabets.

Let denotes the universal Turing machine.

To understand the operation one should determine the program of the simulated Turing machine.

The program basically is the description of the Turing machine, more precisely, the enumeration representation of the transition function.

Let be the Turing machine, we want to simulate, let the cardinality of be and assign to the elements of the numbers , with the assumption that we relate to the initial state . The numbers can be represented over the alphabet , but we will use the notation for them.

The structure of the program of is the following:

, where and are the argument and the value of the transition function , respectively. Such a unit will be called a command of . Furthermore, a command has the following form , if . Of course, the commands should be defined for all possible arguments.

The initial configuration of set by the tape content of ( the first tape) and on tape (i.e. the state corresponding to is written there).

The operation of is divided into phases:

Phase 1: Checking the termination condition.

The Turing machine observes whether the content of tape is among the final states. If yes, then the Turing machine transits to a final state. If no, then the execution continues at phase 2.

Phase 2: State search.

In this phase the Turing machine searches the next command on the program tape such that the state stored on tape is equal to the argument state of the command.

If there are no such a command we continue with phase 5.

Phase 3: Symbol search.

After the actual state is identified, the Turing machine checks if the symbols under the read-write heads on tapes are equal to the symbols of the arguments of the command just found. If yes, then the Turing machine continues with phase 4, if not then it returns to phase 2.

Phase 4: Execution.

The found command contains the description of state transition. The Turing machine copies the state in place of on tape according to the command and by the rest it modifies the content of the first tapes or the position of the read-write heads.

Phase 5: Preparation for the next step.

On tapes and the read-write heads are moved to the front and execution is continued with phase 1.

One can see that the configurations of phase 1 are in one to one relation to the configurations of the Turing machine during its computation. Thus the Turing machine changes the content of tapes and accordingly to the computation of . It terminates if and only if terminates and the output is the same as would have.

The constructed Turing machine is suitable for the one described in the statement of the theorem. ✓

Remark 5.3.

By the results of the previous chapter, every -tape Turing machine 
can be simulated by a -tape one. 
All -tape Turing machine can be simulated by the universal 
Turing machine corresponding to the -tape Turing machines, but this
can be simulated again by a -tape one. 
Hence, one finds that there exists a -tape Turing machine, which 
can simulate all Turing machines. If it is not stated else, this 
Turing machine will be called the universal Turing machine and will
be denoted by .

Definition 5.4.

The language recognized by the universal Turing machine  
is called the universal language and denoted by . 
Formally: . 

By definition, the universal language stands of the words accepted by the universal Turing machine. The universal Turing machine accepts the words in the form , where is a Turing machine program and is an input word accepted by the Turing machine corresponding to . Thus, returning to our original approach, can be regarded as the set of all algorithmically solvable problems together with its all different solutions. One may feel that the above defined universal language is rather complex. Furthermore, the language has the extremal property, that it contains all "solvable problem - solution" pairs and thus it cannot be extended. This property makes the universal language important in computability observations.