What is a universal Turing machine

   
Universal Turing machines


Next:Algorithmic Information Theory - Kolmogoroff Complexity Up:Effective predictability and the Previous:Algorithms are general procedures

As explained in the first section, each algorithm can be described by a suitable Turing machine table. The operation table itself can be interpreted mechanically. So the idea is obvious, a Turing machine U to develop which is the operation table of any Turing machine T can interpret and with it Tsimulated. Such a Turing machine U is also called the universal Turing machine. A universal Turing machine corresponds in its functionality to today's universal computers, which can be reprogrammed as required and then execute their new program. In the following, general considerations will be made about the possibilities of algorithms. In return, the universal Turing machine offers the particular advantage that one can rely on a specific operation table and only has to start from the various possible entries. Thus, all other Turing machines are also taken into account through the possibility of corresponding inputs for the universal Turing machine.

A variant of the so-called Universal Turing Machine Theorems4.14 is the following:


theorem There is a universal Turing machine Uthat computes the following two-digit function: where applies: Let T(A.) a suitable and calculable coding of the Turing machine table of the algorithm A. and e any natural number. Then applies U(T(A.),e)=A.(e). U thus calculates exactly the value that the algorithm has for its two arguments (an algorithm and an input) as the output value A. for input e would calculate.


Should a certain algorithm A. on a given input string e- for example a set of axioms - are applied, this can be done by means of a universal Turing machine U So do it as follows: You write both the operation table T(A.) the Turing machine realization of A. and input e For A. as input to the working tape of U. See figure 3.3.

  

The result of applying the algorithm A. on the input e becomes a possibly infinite string r=A.(e) be that U writes in a specified area of ‚Äč‚Äčtheir work tape. So you can establish a relationship between the input of U, namely T(A.) linked to e and the output r of U produce. Furthermore, the relationship of the number of input characters for U and the length and structure of r produce. This relationship is examined in algorithmic information theory.

Next:Algorithmic Information Theory - Kolmogoroff Complexity Up:Effective predictability and the Previous:Algorithms are general proceduresAchim Hoffmann
2002-07-12