Composition of Turing Machines examples. Correct computability of functions on a Turing machine
The Turing machine (MT) is an abstract executor (abstract computing machine).
Algorithm combinations is the name given to a number of specific ways of constructing new algorithms from several given ones.
Theorems on combinations of algorithms form an important part of the general theory of algorithms. Having been proved once, they allow one to be convinced in the future of the feasibility of complex and cumbersome algorithms without actually writing out the schemes that determine them.
Combinations of algorithms for a Turing machine are described by operations on Turing machines.
1. Composition operation.
Let M 1 and M 2 be Turing machines having the same outer alphabet A« (a 0 ,a 1 ,...,a p ). Let us denote the sets of their states as Q1 « (q 0 ,q 1 ,...,q n ) and Q2 « (q 0" ,q 1" ,...,q m" ).
Definition.
A composition of machines M 1 and M 2 is a machine, denoted M=M 1 ×M 2 , whose program has the alphabet A, the set of states Q« (q 0 ,q 1 ,...,q n ,q n+1 ,... ,q n+m ) and is obtained from the programs of the machines M 1 and M 2 as follows: everywhere in the program of the machine M 1 where there are "triples" with the symbol q 1 (the final state of the machine M 1), it is replaced by the symbol q 0" (the initial state of the machine M 2); all other symbols in the programs of the machines M 1 and M 2 remain unchanged (finally, it remains to renumber all the states of the machine M: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
The composition starts to "work" like a machine M 1 , but in those cases when the machine M 1 should stop, there is a switch to the program of the machine M 2 due to the replacement of q 1 by q 0 ". It is obvious that the composition operation is associative, but not commutative.
Its operation is equivalent to the sequential operation of machines T1 and T2.
The figure shows the composition of Turing machines that implements the superposition operator for n=1 and m=1.
Picture 1.
Definition.
An iteration of a Turing machine M is the machine
2. Branch operation.
Let M 1 , M 2 and M 3 be Turing machines having the same external alphabet A« (a 0 ,a 1 ,...,a i ,...,a j ,...,a p ) and, accordingly, sets of states : Q1 « (q 0 ,q 1 ,...,q n ), Q2 « (q 0" ,q 1" ,...,q m" ), Q3 « (q 0", q 1" ,... ,q l" ).
Definition.
The result of the branching operation on Turing machines M 1 , M 2 and M3 is the Turing machine M, the program of which is obtained from the programs of the machines M 1 , M 2 and M 3 as follows: the program of the machine M1 is written, then the programs of the machine M 2 and M 3 are assigned. If the symbol a i is observed in the final state q 1 of the machine M1, then control is transferred to the machine M 2 , i.e. the symbol q 1 is replaced by the symbol q 0" and the machine M 2 starts working. If, however, the symbol a j is observed in the final state q 1 of the machine M 1, then control is transferred to the machine M 3, i.e. the symbol q 1 is replaced by the symbol q 0" and machine M 3 starts to work. All other characters in the programs of machines M 1 and M 2 remain unchanged. The machine M terminates in the final state q 1 (in conclusion, it remains to carry out a continuous renumbering of the states of the machine M).
The result of the branching operation on the Turing machines M 1 , M 2 and M3 is denoted as follows:
For two-letter Turing machines (Turing machines with a two-letter alphabet), the branching operation on arbitrary Turing machines M1 , M2 and M3 is denoted as follows:
those. if the symbol a 0 is observed during the operation of the machine M1 in the state q 1 , then control is transferred to the machine M2 , otherwise, to the machine M3.
3. Cycling operation.
Let M be a Turing machine with alphabet A« (a 0 ,a 1 ,...,a p ) and state set Q« (q 0 ,q 1 ,...,q n ).
Definition.
The result of the looping operation will be called the Turing machine, denoted by (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2,3,..., n)
whose program is obtained from the program of the machine M by replacing the command q i a j ®q 1 a t r, rн(L,R,L), t=0,1,2,...p, the symbol q 1 with the symbol q s in the consequent e.
2.4 Turing machine variants
The Turing machine model allows extensions. One can consider Turing machines with an arbitrary number of tapes and multidimensional tapes with different constraints. However, all of these machines are Turing complete and are modeled by a regular Turing machine.
As an example of such an equivalence, consider the reduction of any MT to a MT operating on a semi-infinite tape .
Theorem: For any Turing machine, there is an equivalent Turing machine running on a semi-infinite tape.
Proof:
Consider Yu. G. Karpov's proof. The proof of this theorem is constructive, that is, we will give an algorithm by which, for any Turing machine, an equivalent Turing machine with a declared property can be constructed. First, we arbitrarily number the cells of the MT working tape, that is, we determine the new location of information on the tape:
Picture 1.
Then we renumber the cells, and we will assume that the symbol "*" is not contained in the MT dictionary:
Picture 1.
2.5 Turing computability and decidability
It was proved above that the classes of functions computable using recursive functions, Turing machines, or normal Markov algorithms coincide. This allows us to consider the concept of "computational algorithm" invariant to the method of description. Differences are observed only in the use of algorithmic objects. If for recursive functions the objects are numbers and numerical functions, and the calculation process is specified by the operators of superposition, recursion, minimization and iteration, then for Turing machines such objects are symbols of the alphabets of external and internal memory, and the calculation process is specified by a protocol using the exit, transition and head movement. For a normal Markov algorithm, such objects are words or character sequences, and the computation process is specified by substitution rules or products that change the composition and structure of the original character sequence to the desired result.
An arithmetic (numerical) function is a function whose range is a subset of the set N, and whose domain is an element of the set N.
For algorithmic problems, a typical situation is when you need to find an algorithm for calculating a numerical function f(x 1 , x 2 , …, x n) depending on the integer values of the arguments x 1 , x 2 , …, x n .
A function f:N n →N is called computable if there is an algorithm that allows for any set of values of its arguments to calculate the value of the function (or indicate that the function is not defined on this set). Since the definition of a computable function uses the intuitive concept of an algorithm, the term "intuitively computable function" is often used instead of the term "computable function". Thus, a mass problem has a solution if the arithmetic function corresponding to this problem is intuitively computable.
The function f(x 1 , x 2 , …, x n) is called effectively computable if for the given values k 1 , k 2 , …, k n of the arguments, you can find the value of the function f(k 1 , k 2 , …,k n) using some available mechanical procedure (algorithm).
Instead of clarifying the concept of an algorithm, one can consider a refinement of the concept of "computable function". Usually, they act in the following way:
1. An exactly defined class of functions is introduced.
2. Make sure that all functions from this class are computable.
3. Accept the hypothesis (thesis) that the class of computable functions coincides with the introduced class of functions.
A function is called computable if there is an algorithm that calculates it. "Computability" is one of the basic concepts of the theory of algorithms, invariant to the computed function and algorithm. The difference between a computable function and an algorithm is the difference between the description of a function and the way in which its values are calculated given the values of the independent arguments.
Turing's thesis. Any intuitive algorithm can be implemented using some Turing machine.
It follows from Turing's thesis that if algorithmic problems arise, then they should be solved on the basis of the construction of Turing machines, that is, a formalized concept of an algorithm is sufficient. Moreover, in algorithmic problems it is often not about the construction of an algorithm, but about the computability of some functions constructed in a special way.
It should be noted that in these cases it is sufficient to use the alphabet (0,|), where 0 is an empty character. For example, natural numbers, including 0, are encoded in this alphabet as follows: 0 - |; 1 - ||; 2-
N - ||…| (n + 1 times). A partial numeric n local function f(x1 , x2 , …, xn) is called Turing computable if there is a machine M that computes it in the following sense: 1. If the set of argument values
THE PROBLEM OF SELF-APPLICABILITY
According to the definition of a Turing machine, this is the triple T=
P: qi a aj a ® q r a a s a S t a , a = 1, 2, …, k , Where S1-R, S2-L, S3- C . (*)
In this case, we can assume that there are some common alphabets A0 And Q0, in which characters are written a And q for all Turing machines. Then the symbols qi a, aj a , q r a, a s a, S t a are symbols of alphabets A0 And Q0.
This approach allows all Turing machines to be numbered, that is, to assign to each machine a certain number (code) inherent only to this machine, by which it would be possible to distinguish it from other machines. Here we consider one of the ways of numbering.
Gödel numbering of Turing machines. Let p1, p2, p3 , … - a sequence of prime numbers arranged in ascending order, for example, 2, 3, 5, 7, 11, 13, …
Turing machine number with program (*) called a number
n(T) = .
Example
A machine that implements a function S(x)= x + 1 , has a program in the alphabet {0, } . The number of this program, taking into account the fact that a 0 = 0 , a 1= | number will be:
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Obviously, not all natural numbers are Turing machine numbers. On the other hand, if n is the number of some machine, in general alphabets, then its program can be uniquely restored from this number.
Car T applied to the word n(T)(that is, to the code of your own number), called self-applicable .
It is possible to build both self-applicable machines and non-self-applicable machines. For example, the machine from the given example is self-applicable. Car T, which does not have a break character in the right parts of the program (in the body of the table), is not applicable to any word, and, consequently, to the word n(T).
The problem of self-applicability consists in the following: to indicate an algorithm that, given any Turing machine, would determine whether it is self-applicable or not.
According to Turing's Thesis, such an algorithm should be sought in the form of a Turing machine. This machine should be applicable to the number codes of all Turing machines, and depending on the result of processing the codes of the tested machines, it would have different final configurations.
Let, for example, this machine T applied to code n(T * ) . If the machine T * self-applicable, then the final configuration of the machine T has the form a" q0 | B", and if the machine T * is not self-applicable, then the final configuration of the machine T has the form a" q0 0B ". Here a", B", a", B"- words.
Theorem The problem of self-applicability is algorithmically unsolvable, that is, there is no Turing machine that solves this problem in the above sense.
It follows from the theorem that there is no general algorithm for solving the problem of self-applicability. In specific particular cases, such algorithms may exist.
Let us use the results of this theorem to prove the undecidability of the problem of applicability to the initial word.
The problem of applicability to the initial word consists in the following: create an algorithm that, by machine T and word X would install, applicable machine T by the way X or not (otherwise a halt problem).
In terms of Turing machines, similarly to the formulation of the problem of self-applicability, this problem is formulated as follows: is it possible to build a machine that would be applicable to all words of the form n(T)0 X , Where T random machine, X is an arbitrary word, and if the machine T applicable to the word X a" q0 |B" , and if the car T does not apply to the word X , would lead to the final configuration a" q0 0B" . Here a" , B" And a", B"- arbitrary words.
Theorem The problem of applicability to the initial word is algorithmically unsolvable, that is, there is no Turing machine that solves this problem in the above sense.
As stated above for the self-applicability problem, the first preliminary step is numbering. Therefore, below this issue is consistently considered and solved for algorithms and its three main types of algorithmic models.
Algorithm numbering
The numbering of algorithms plays an important role in their study and analysis. Since any algorithm can be specified as a finite word (represented as a finite sequence of symbols of some alphabet), and the set of all finite words in a finite alphabet is countable, then the set of all algorithms is also countable. This means the existence of a one-to-one mapping between the set of natural numbers and the set of algorithms, that is, the possibility of assigning a number to each algorithm.
The numbering of algorithms is at the same time the numbering of all algorithmically calculated functions, and any function can have an infinite number of numbers.
The existence of numbering makes it possible to work with algorithms in the same way as with numbers. Numbering is especially useful in the study of algorithms that work with other algorithms.
Let there be a certain mass problem with a set of initial objects X and a set of desired objects Y. For the existence of a solution to the mass problem, it is necessary that the elements of the sets X and Y be constructive objects. Therefore, the elements of these sets can be enumerated by natural numbers. Let x∈ X be some initial object, denote by n(x) its number. If in the mass problem it is required to obtain the desired object y∈ Y with the number n(y) from the initial object x, then we define an arithmetic function f: Nn →N such that f(n(x))=n(y).
As an example of constructing arithmetic functions for mass problems, consider mass problems.
1. If an array ] of natural numbers is given, then it can be associated with a natural number 2x1, 3x2,... p(n)xn , where p(n) is the n-th prime number. Consider for example an array of length 5:
] 2x13x25x37x411x5.
This numbering defines the arithmetic function f (for example, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Any rational number has some natural number. The enumeration of the set of desired objects of the problem is trivial:
("yes", "no") a (1, 0). For a given mass problem, you can build an arithmetic function of one argument using the trick from the previous example, or you can consider a function of three arguments (three numbers of elements of the original triple).
3. The numbering of program texts can be done as follows: any program can be perceived as a record of a number in the 256-ary number system (if the ASCII table characters were used to write the program).
The transition from a mass problem to an arithmetic function allows us to reduce the question of the existence of a solution to the mass problem to the question of the existence of an efficient way to calculate the values of an arithmetic function from its argument(s).
Numbering of sets of numbers
In the theory of algorithms, a technique has become widespread that makes it possible to reduce the study of functions of several variables to the study of functions of one variable. It is based on the enumeration of sets of numbers so that there is a bijective correspondence between sets of numbers and their numbers, and the functions that determine its number from a set of numbers and from the number of the set of numbers themselves are general recursive. For example, for a function containing two independent variables (x, y), this mapping h(x, y) might look like this:
Picture 1.
Let the pairs (x, y) form a partially ordered set N (2) . Given h(x, y) = n, then there is an inverse mapping: x = h -1 1 (n) and y= h -1 2 (n), i.e. h(h -1 1 (n), h -1 2 (n)) = n. This allows calculating the number n for any pair (x, y) and vice versa, using the number n to calculate the values of x and y:
Using these rules, one can calculate the numbering of triples h 2 (x, y, z) = h(h(x, y), z) = n and, conversely, by the number of the triple - the values x, y, z. For example, if h 2 (x, y, z) = n, then z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 (h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n))) , h -1 2 (n)). The triples (x, y, z) form a partially ordered set N (3) . Similarly, for an arbitrary number of numbers we have:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). If h n-1 (x1, x2,…, xn)=m, then xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ................................., x2 = h -1 2 (h -1 1 (... h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
Having the numbering of sets of sets N (1) , N (2) ,..., N (i) ,..., N(n , where N (i) is the set of sets of (i) numbers, one can establish a combined numbering of arbitrary sets numbers M = N (1) N (2) ... N (i) .. N(n) , where M N. For any n N we have h(x1,x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
If h(x ,1x ,2..., x)n = m, then h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Using the above formulas, you can recover the values of x1, x2,…, xn.
Similar information.
Definition, operation and ways of defining a Turing machine
A Turing machine is understood as some hypothetical (abstract) machine consisting of the following parts (Fig. 3.1.)
1) an endless tape in both directions, divided into cells, each of which can contain only one character from the alphabet, as well as an empty character l;
2) a control device (working head), which at any moment of time can be in one of the states from the set . In each of the states, the head is placed opposite the cell and can read (view) or write a letter from the alphabet into it A.
Rice. 3.1. Turing machine
The functioning of the MT consists of a sequence of elementary steps (cycles). Each step does the following:
1. the working head reads (views) the character;
2. Depending on its state and the observed symbol, the head generates a symbol and writes it to the observed cell (possibly =) ;
3. the head moves one cell to the right (R), left (L) or stay put (E);
4. The head enters a different internal state. (possibly =).
The state is called initial, - final. When entering the final state, the machine stops.
The complete state of the MT is called configuration . This is the distribution of letters in the cells of the tape, the state of the working head and the monitored cell. Configuration in tact t is written as: , where is the subword to the left of the monitored cell, is the letter in the monitored cell, is the subword to the right.
The initial configuration and the final are called standard.
There are 3 ways to describe the operation of the MT:
View command system
Function table;
Graph (diagram) of transitions.
Let's look at them with examples.
Example 1 Construct a MT that implements the concatenation of two words in the alphabet . The words on the tape are separated by * . The initial configuration is standard.
The MT command system has the form:
In the state, the head moves to the right to an empty character.
The rightmost character is erased.
The asterisk is erased if the first word is empty.
The right word is shifted to the left by one position character by character.
Switching to the standard target configuration.
Function table
| a | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
Dashes in the table mean that l cannot be encountered in states.
|
|
|||
Standard final configuration.
The computation of a dictionary function on the MT will be understood as follows. Let the word a be written on the tape in the initial configuration. If the value is defined, then after a finite number of steps (cycles) the machine must go to the final configuration, in which the word is written on the tape. Otherwise, the MT should run indefinitely.
Using MT, you can describe the performance of arithmetic operations on numbers. In this case, numbers are presented on the tape as words in an alphabet consisting of digits of some number system, and separated by a special sign that is not included in this alphabet, for example, *. The most commonly used system is unary, consisting of one character -1. The number X on the tape is written in the word, (or abbreviated) in the alphabet A=(1).
A numerical function is correctly computable (or simply computable) in the sense of Turing if there is an MT that takes the configuration to the configuration when = y, or runs indefinitely when not defined.
Example 2 The operation of adding two numbers in unary code.
Initial configuration:
Final configuration: i.e. addition actually boils down to assigning a number b to the number a. To do this, the first 1 is erased and * is replaced by 1.
We give a description of MT in the form of a functional table:
| * | l | ||
| - | |||
| - | |||
| - |
The above methods of describing MT can practically be used only for simple algorithms, since for complex descriptions becomes too cumbersome. Similarly, describing recursive functions with only the simplest functions and operators of superposition, primitive recursion, and minimization would be extremely cumbersome. Therefore, the primitive or partial recursiveness of a function is proved using other functions whose primitive or partial recursiveness has already been proven.
Similarly, Turing machines for complex algorithms can be built using existing MTs. Such a construction is called the MT composition.
Let us describe 4 main ways of MT composition:
Sequential composition (superposition);
Parallel composition;
Branching
Consistent composition machines and that compute dictionary functions and in the alphabet A, is called a machine T, which calculates the function . Sequential composition is depicted as follows:
and is denoted.
Sequential composition is usually used to describe the linear sections of algorithms.
Proof of the theorem on the possibility of constructing a machine T, which is a sequential composition of two arbitrary machines and is carried out by identifying the final state with the initial state .
Example 3 Construct a 2*X multiplication algorithm in unary code using a copy machine that translates the word a into the word a*a and an addition machine. The desired MT looks like this:
| | | |
|||||||||||||
| | |
||||||||||||||
Parallel composition machines and that compute dictionary functions and in alphabets A And IN respectively, the name of the machine T, which calculates the dictionary function . Here the sign is used to separate words in parallel MT composition.
| |
and is marked: .
In fact, a parallel composition of two MTs receives as input a word consisting of 2 words in different alphabets and outputs a word consisting of 2 words, i.e. consists of two simultaneously and independently operating machines.
To implement a parallel composition, a machine with a double-decker tape is used. The need for this is due to the fact that the calculation of and occurs sequentially in time, and calculated, for example, first, may require more space than a, and spoil the word b. The double-deck tape machine works like this: the word b is rewritten to the second floor and erased on the first floor, computed on the first floor, computed on the second floor, and then rewritten to the first floor, possibly with a shift.
To implement parallel composition n machines used n– floor tape.
The MT team with a two-story tape is written as follows:, where are the letters written on the first and second floors, respectively.
Example 4. Implement parallel composition of machines and , computing functions in the binary system and a+b in the unary system.
The input word has the form: .
Let us describe the operation of the MT by a system of commands:
Movement to the right to the word b
Rewriting the word b to the second floor
Move left to word a
Adding 1 to X.
Movement to the right to the word b.
Census b to 1st floor with simultaneous addition of numbers a And b.T respectively. Commands in curly braces added to the command system
The final state of the entire MT.
It should be noted that in all cases at the beginning of the algorithm it is necessary to insert a check of the initial data for special values (most often for 0), failure to comply with this requirement can lead to a loop.
The MT composition can be used to construct complex algorithms. The question arises: can any algorithm be implemented as a composition of MT? The answer to this question is Turing thesis , an analogue of Church's thesis: any algorithm can be implemented using Turing machines and vice versa, any process implemented by a Turing machine is an algorithm.
Turing's thesis is not a theorem, it is impossible to prove it, because it contains the informal notion " algorithm". However, long-term mathematical practice is a reliable confirmation of this thesis: for 50 years, no algorithm has been found in an intuitive sense that could not be implemented using Turing machines.
Goal of the work: gain practical skills in writing algorithms using the composition of Turing machines.
Theoretical background
The above methods of describing MT can practically be used only for simple algorithms, otherwise the description becomes too cumbersome. Turing machines for complex algorithms can be built using the already existing elementary MTs, and such a construction is called composition MT.
Let us describe 4 main ways of MT composition:
Sequential composition (superposition);
Parallel composition;
Branching
1. Sequential composition of Turing machines
Consistent composition or superposition Turing machines and 
And 
in the alphabet A, called the car M, which calculates the function 
.
Sequential composition is depicted as follows:
and denoted 
or 
.
2. Parallel composition of Turing machines
Parallel composition
machines 
And 
, computing dictionary functions 
And 
in alphabets A And IN, respectively, the name of the machine M, which calculates the dictionary function . Here sign 
used to separate words in parallel MT composition.
Parallel composition MT 
And 
depicted as follows:
and is denoted: 
.
In fact, a parallel composition of two MTs receives as input a word consisting of 2 words in different alphabets, and at the output it produces a word also consisting of 2 words, i.e. consists of two simultaneously and independently operating machines. To implement a parallel composition, a machine with a double-decker tape is used.
The double deck tape machine works as follows:
1) word 
rewritten on the second floor of the tape and erased on the first,
2) calculated 
on the first floor,
3) calculated 
On the second floor
4)
rewritten to the first floor, possibly with a shift.
The MT command with a double-deck tape is written as follows:
,
Where 
- letters written respectively on the first and second floors. Denote the word lengths 
, respectively, 
.
We will demonstrate the operation of the Turing machine with a double-deck tape. In general, word lengths 
And 
do not coincide with each other, but for simplicity of the image we assume that they are equal. Then the implementation of points 1)-4) on the MT with a two-story tape is performed as follows:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
To implement parallel composition n Turing machines are used n– floor tape.
3. Branching or conditional branching in the composition of Turing machines
Given Turing machines 
And 
, computing dictionary functions 
And 
, and the machine 
, which evaluates some predicate P(
)
with recovery (i.e. without erasing the word
),
then a Turing machine can be built to implement the branching 
, which calculates the function:
The branching of Turing machines on the composition diagrams is depicted as follows:
and denoted 
, Here 
- the result of the machine 
, which takes the values "1" if the predicate P(
)=
”true”
and "0" if the predicate P(
)=
“false”
,
is a Turing machine that implements copying of the input word 
.
4 . Cycle in the composition of Turing machines
Cycle in the composition, MT is implemented according to the same principles as branching.
" Bye P(
)=
”true”
, fulfill 
»,
Where
- the word on the tape before the first execution 
and after the next execution .
For the image of the cycle, we introduce some notation, let:
is a Turing machine that implements the calculation of the predicate P(
)
;
–MT that implements copying of the input word 
;
–MT, executed in a cycle and realizing 
;
–MT, executed when exiting the loop and realizing 
.
Then, the cyclic composition of Turing machines, or cycle, can be depicted as follows:
Programming with compositions of Turing machines:
1) construction of block diagrams of complex algorithms of such a degree of detail that their blocks correspond to elementary MTs;
2) construction of elementary MTs that implement simple blocks;
3) combining elementary MTs into a composition of MTs.
Example. Construct a MT composition that implements 
.
– Turing machine that implements copying of the input word;
–MT, which implements the function of setting the constant to zero;
–MT computing predicate with recovery 
;
– MT that implements the selection function 
-that argument from 
arguments
–MT, which implements the function of decreasing the argument 
by 1 in unary code (wipes the leftmost character);
– MT that performs the addition of two numbers in a unary code.
It should be noted that in any case, at the beginning of the algorithm execution, it is necessary to check the input data for correctness (for example, the equality of the argument to 0 when dividing).
Figure 1.6
Figure 1.6 uses the following notation:
T 1, T 2 - Turing machines;
ST 1 , ST 2 - command systems of machines T 1 and T 2, respectively;
x - initial information for the machine T 1 ;
T 1 (x) - the result of the machine T 1;
T 2 (T 1 (x)) - the result of the work of the machine T 2.
Consider, for example, the composition of two machines, the first of which performs the operation of copying, and the second - the operation of adding numbers in a unary code. The scheme of combining machines and an example of a tape with the results obtained is shown in Figure 1.7.
Figure 1.7
The composition shown in Figure 1.7 allows you to perform the operation of doubling a number using already known copying and addition machines. Thus, having compiled algorithms for Turing machines to solve a set of certain operations (for example, arithmetic operations), then one can compose Turing machines to solve more complex problems. At the same time, the development of a general algorithm is reduced to its compilation from those operations for which algorithms for execution on a Turing machine are already known. This approach is similar to using procedures and functions in programming.
However, the use of the composition of machines assumes that the algorithms for performing elementary operations are known, from which the general algorithm is composed. Therefore, when solving arbitrary problems, this approach does not exclude the need to develop new algorithms and, accordingly, the development of Turing machines with different control units. It is possible to implement any algorithm without changing the structure of the control unit using the universal Turing machine.
1.2.2 Universal Turing Machine
If some Turing machine is given (i.e., the alphabets of input, output signals and states, the initial position of the head and the initial state of the machine, as well as the table of operation of the machine and the tape with initial information are known), then it is possible to manually perform all the information transformations step by step, for for which this machine is intended. In fact, in this case, the simulation of the Turing machine is performed.
When analyzing the operations that are performed in the simulation of a Turing machine, it can be established that the simulation is reduced to repeating the following actions at each step:
ÄReading a character from the tape cell over which the head is located.
ÄSearch for a command in the machine operation table. The search is performed by the current state of the machine and the value of the read character.
ÄSelect from the command the character to be written to the tape and write it.
ÄSelecting the head movement symbol from the command and moving it.
ÄSelecting a new machine state from the command and changing the current state to a new one. This is followed by the transition to the next step and the repetition of these steps.
|
|
 |
|||||
 |
|||||
Figure 1.8
The nature of these elementary operations is such that they can all be performed by some other Turing machine that will simulate the operation of the original machine. The essence of modeling is explained in Figure 1.8.
If a machine T has an instruction set ST and processes a tape with information X, then its operation can be simulated by another machine U which has its own instruction set SU. For simulation, at the input of the machine U, it is necessary to submit not only a tape with information X , but also the command system (work table) ST. This command system can be recorded on the same tape as the original information.
 |
Figure 1.9
An important feature of the simulation machine is that its command system SU (and, accordingly, the structure of the control unit) does not depend on the algorithm of the simulated machine T. A Turing machine that can simulate the operation of any other Turing machine is called universal. A variant of the structure of the universal Turing machine (UMT) is shown in Figure 1.9.
The UMT tape is divided into three zones: the data zone, the mode zone and the command zone.
The data zone contains the initial information to be processed by the simulated Turing machine. In the same zone, the results of the work of the UMT are recorded.
The mode zone contains the current state Q t and the current input symbol X t that was read from the data zone cell in a given cycle.
The command zone contains the system of commands for the simulated machine. The commands are sorted into groups. The first group includes commands beginning with the character Q 0 , the second - with the character Q 1 and so on. Within each group, the commands are ordered by the value of the character X t . Thus, the commands on the tape are arranged as they are placed in the table of operation of the simulated machine.
Reading information from the tape and writing to the tape are performed using three heads: D d - data head, G r - mode head, G c - command head. Each head can move on its own zone of the tape.
Before the start of UMT operation, relevant information must be recorded in each zone of the tape. Heads must be mounted above the left symbol in each zone.
The work of UMT occurs in cycles, in each cycle the execution of one command of the simulated machine is simulated. The UMT work graph is shown in Figure 1.10.
 |
Figure 1.10
Figure 1.10 uses the following notation:
Q G to P (G to L, G r P, G r L, G d P, G d L) - moving one of the heads
right or left;
Q (G to), (G d), (G r) - information read by one of the heads;
Q (G to) à (G r) - reading data by the command head and writing this data
using the mode head to the tape mode area;
Q a is an auxiliary variable that takes the value 1, es-
whether the characters read by the heads Г to and Г р coincide;
Q in - an auxiliary variable that takes the value 1, es-
whether the symbols of the current (Q t) and final (Q z) states are the same
Q p is a signal that takes on the value 1 if the command head at
moving to the left went beyond the borders of the command zone;
The following steps are performed in each UMT cycle:
u search for the command zone;
u search for a team in the zone;
u simulation of command execution.
The command zone search begins by comparing the current state Q t from the mode zone with the state Q i recorded at the beginning of the first command in the command zone. If these states are not equal, then the command head moves to the beginning of the next command, for which five head steps to the right are performed (states U 0 - U 4). If the characters Q t and Q i match, the head of the commands is at the beginning of the first command of the desired zone. Next, the search for a command corresponding to the symbols Q t and X t of the mode zone begins. To do this, the mode head is set over the mode zone character X t, and the command head is placed over the X i character in the current command.
Searching for a team in a zone is performed in the same way as searching for a team zone. In this case, the command head moves to the right by five steps (states U 5 - U 9) until the characters X t and X i are compared.
Command execution (states U 10 - U 17) begins with moving the command head one step to the right, after which the Y t character read from the found command is written to the data zone using the data head instead of the previously read character X t . After the next step of the command head to the right, the data head movement symbol (Y d) is read from the found command and the data head is moved in accordance with this symbol (P, L). Below it is the next processed character (X t +1), which is written to the mode zone with the help of the mode head to prepare the next cycle. Next, the command and mode heads are set so that the next state Q t +1 can be written to the mode zone (states
U 14 , U 15). In state U 16, the condition for terminating the decision is checked. If the symbol of the next state does not match the symbol of the final state of the simulated machine (Q z), then the solution of the problem is not completed, and in the state U 17 the command head moves to its original position (to the beginning of the first command of the first zone). In this case, the UMT is ready to perform the next cycle, i.e. to simulate the execution of the next command.
If the symbols Q t and Q z coincide, the solution of the problem ends and the UMT goes into the final state U z .
When analyzing the UMT operation process, an important conclusion can be drawn that the algorithm of the UMT operation does not depend on what particular problem the simulated Turing machine solves. Therefore, the structure of the UMT control unit does not change when simulating various machines, i.e. does not depend on the tasks to be solved. That is why the UMT is indeed a universal machine with which to execute any algorithm without changing its structure.
Since the process of choosing the next UMT command and its execution is connected with sequential enumeration of tape cells, solving problems on UMT requires too much time. Therefore, the Turing machine, including the universal one, was never built, but it is easy to see in it an analogue of modern computers. So the command system in the UMT command zone is similar to the machine program, while the pair of symbols Q t and X t play the role of the address of the machine command.
However, the Turing machine is a rather convenient tool for describing algorithms and is widely used in the theory of algorithms.
Control questions
ü1.What is the composition of Turing machines?
ü2.What is the composition of Turing machines used for?
ü3. Can one Turing machine simulate the operation of another machine
Turing?
ü4. What actions are performed in this case?
ü5.Explain the structure of the universal Turing machine?
ü6. What information is recorded in the zones of the UMT tape?
ü7.What is the Turing machine instruction set?
ü8. What steps does the UMT work cycle contain?
ü9.Explain the contents of the step "search command zone".
ü10.Explain the contents of the step "command execution".
ü11. What are the features of the information processing process using
The diagram looks like a graph:
Machine table value
Table 1
Some operations on Turing machines
The operation of the Turing machine is completely determined by the initial data and the command system. However, in order to understand how a particular machine solves a problem, as a rule, there is a need for meaningful explanations such as those given for the machine. 
. These explanations can often be made more formal and precise by using flowcharts and some operations on Turing machines. Recall that the composition of functions 
And 
called a function 
, which is obtained by applying 
to the calculation result 
. In order to 
was determined with this 
, is necessary and sufficient for 
was determined on 
, A 
was determined on 
.
Theorem 1. If 
And 
are Turing computable, then their composition 
is also Turing computable.
Let 
- a machine that calculates 
, A 
- a machine that calculates 
, and the set of their states, respectively 
And 
.
Let's build a transition diagram of the machine 
from charts 
And 
as follows: identify the initial vertex 
machine diagrams 
with end point 
machine diagrams 
(for instruction systems, this is equivalent to the fact that the instruction system 
assign to the command system 
and for this 
in teams 
replace with 
). We get a diagram with ( 
) states. initial state 
let's announce 
and final 
. For simplicity of notation, we will assume 
And 
numerical functions of one variable.
Let 
defined. Then 
And
. Car 
will go through the same sequence of configurations with the difference that instead of 
she will pass in 
. This configuration is the standard initial configuration for the machine. 
, That's why 
. But since all teams 
contained in 
, That
and hence 
. If 
not defined, then 
or 
does not stop and, therefore, the machine 
will not stop. So the car 
calculates 
.
The machine built in this way 
will be called the composition of machines 
And 
and designate 
(or 
(
)), as well as to depict in a block diagram:
Composition of Turing machines
Let 
,
,
- three Turing machines with the same external alphabet 
, with alphabets of internal states 
,
,
and programs 
,
,
respectively.
Composition
machines 
And 
called carT
, whose program is the union of the sets 
And
, Where 
denotes the set of commands received from 
replacing all 
on 
.
Turing machine forks
branching machines
,
,
By 
, symbolically
called carT
, whose program is obtained as follows: from 
commands are excluded 
And 
For 
, the resulting set will be called 
; Then.
Universal Turing Machine
The instruction set of a Turing machine can be interpreted both as a description of the operation of a particular device and as a program, i.e. a set of prescriptions that unambiguously lead to a result. When analyzing examples, the second interpretation is unwittingly accepted, i.e. we act as a mechanism that is able to reproduce the work of any Turing machine. The certainty that they will all do it in the same way (if they do not make mistakes, which, by the way, is also assumed in the operation of a Turing machine) is essentially the certainty that there is an algorithm for reproducing the operation of a Turing machine according to a given program, i.e. command system. Indeed, it is not difficult to give a verbal description of such an algorithm. Its main action is cyclical and consists of the following: "For the current configuration 
find in the command system a command with the left side 
. If the right side of this command is 
, then replace in the current configuration 
on 
(it turns out the configuration 
); if the right side has the form 
, then replace 
on 
. The verbal description of the algorithm may be inaccurate and needs to be formalized. Since a Turing machine is now being discussed as such a formalization of the concept of an algorithm, it is natural to pose the problem of constructing a Turing machine that implements the described reproduction algorithm. For Turing machines that compute functions of one variable, the formulation of this problem is: build a Turing machine 
, which calculates a function of two variables and such that for any machine 
with command system 
, If 
defined (i.e. if the machine 
stops at initial data 
) And 
does not stop if 
does not stop. Any machine with the above property will be called universal Turing machine. It is easy to generalize this formulation to any number of variables.
The first problem that arises when building a universal machine 
, is related to the fact that 
like any other Turing machine, must have a fixed alphabet 
and a fixed set of states 
. Therefore, the command system 
and the initial data of an arbitrary machine 
can't just be transferred to the tape machine 
(there is always a car 
, alphabets 
And 
which is superior in power 
And 
or simply do not match).
The way out is to characters from 
And 
encoded by characters in the alphabet 
. Let 
,
. We will always assume that 
And 
(these two characters are always in the alphabet of any machine that works with numbers). Denote the codes 
And 
through 
And 
and define them as 
; for anyone else 
; for the final state 
, If 
. Code 
for this machine 
always has a length (format) 
, and the code 
- format 
. Symbols 
,
let's introduce into 
, i.e. 
,
,
. Symbol code 
, formed by the codes of the characters that make up this word, denote 
. Thus, the final refinement of the formulation of the problem of a universal machine 
comes down to the fact that for any machine 
and words 
alphabet 
.
The existence of a universal Turing machine means that the instruction set 
any car 
can be interpreted in two ways: either as a description of the operation of the original device 
, or as a program for a universal machine 
. For a modern engineer designing a control system, this circumstance is natural. He knows well that any control algorithm can be implemented either in hardware - by building an appropriate circuit, or in software - by writing a program for a universal control computer.
However, it is important to realize that the idea of a universal algorithmic device is completely unrelated to the development of modern technical means for its implementation (electronics, solid state physics, etc.) and is not a technical, but a mathematical fact that describes in abstract mathematical terms that do not depend on technical means, and, moreover, based on an extremely small number of very elementary initial concepts. It is characteristic that the fundamental works on the theory of algorithms (in particular, the work of Turing) appeared in the 30s, before the creation of modern computers.
This double interpretation preserves at the abstract level the main pros and cons of the two options for engineering implementation. concrete machine 
works much faster; in addition, the control device of the machine 
rather cumbersome (i.e., the number of states and commands is large). However, its value is constant and, once built, it is suitable for the implementation of arbitrarily large algorithms. All that is needed is a large amount of tape, which is naturally considered cheaper and more simply arranged than the control device. In addition, when changing the algorithm, you do not need to build new devices, you just need to write a new program.