Which functions can a Turing machine emulate

A universal Turing machine

Turing machines as special processing systems

So far, we have used Turing machines as special processing systems: a special Turing machine was developed for each problem.

To clarify, let's consider the problem of inverting a 0-1 string.


Note that the end of the 0-1 sequence to be processed is marked here with the symbol "#".

A Turing machine to solve this particular problem is easy to construct.

Task 1

Test this Turing machine.

Technical concept - universal Turing machine

With the Turing machine as a computational model, have we actually captured what real computers are at their core, if we disregard convenient input, output and storage options?

An essential property is not yet recognizable. Real computers are programmable systems.

You are able to run any given program with any given data. So they are universal in the sense that they are designed not only for one task, but to execute any solution algorithm.

Is the Turing machine calculation model also able to function as a programmable system? There would then have to be a "universal Turing machine" that works as a kind of Turing machine interpreter.

A universal Turing machine has the ability to simulate any other Turing machine. As input, it receives the description of the Turing machine to be simulated and the data on the input tape for this Turing machine. The universal Turing machine then generates the data that the Turing machine to be simulated would generate when processing the transferred data.

exercise 2

If you click the [Tasks] button in the TuringKara world window, you get a selection menu with many tasks, from easy to very difficult. The task "The Universal Turing Machine" is one of the very difficult ones.

(a) Select the world "Invert a character string" and execute the given control program. The way this Turing machine works is initially somewhat opaque. But with a little patience you can see some behavioral patterns. In particular, can you understand how a character string is inverted here?

(b) Now read the notes under "Coding". Here you can find out how a (simple) Turing machine is represented on the two-dimensional grid.

(c) If you have understood everything, then you should be able to simulate a (simple) Turing machine for doubling a number of lines with the universal Turing machine.

A universal Turing machine

They actually exist, Turing machines that simulate the behavior of any given Turing machine.

The figure shows a possible control program. This program is tailored for the coding of Turing machines (including the tape) shown in the following figure.

Note that the Turing machines to be simulated here must be simple single-band Turing machines, while the universal Turing machine here is a two-dimensional Turing machine.

It can be shown that there are also universal Turing machines in the form of simple single-band Turing machines. however, the proof is quite complex and should therefore not be provided here. We limit ourselves to the formulation of fundamental knowledge.

Theorem (about the existence of universal Turing machines)

There is a (simple) Turing machine which, as a universal Turing machine, can simulate any other (simple) Turing machine.

This shows that the Turing machine calculation model is so powerful that it can provide programmability. Despite its simplicity, the Turing machine is therefore a serious candidate for specifying the "idea of ​​the computer".


We want to go one step further by asking the following question: Is the Turing machine computational model so powerful that it can execute all conceivable algorithms (in a suitably coded form)? The clarification of this question will occupy us in the following section.