     TURING - description.

     It is known that there are several formalization of the notion
of algorithm (Markov's normal algorithms, recursive functions,
Turing machines, etc.) which were found to be equivalent to each other.
In other work, if something can be calculated via Turing machines,
it can be calculated via normal algorithms, etc.
     In this connection interesting is the so-called normalization
hypothese which states that each of these formalizations is exhaustive,
i.e., does not exist whichsoever algorithm in "intuitive" sense
which would not be equivalent to some normal algorithm (Turing
machine, etc.).
     In this sence, it is interesting to look at simplest formal
algorithms: what do they do, whether they can be used for, e.g.,
obtaining of fine visual effects.
     Recollect that the traditional Turing machine works as follows. 
There is a tape divided to cells; in each of these cells one can 
write numbers from 1 to nl; there is head which can move from cell 
to cell and read/write numbers in the cells; and there is a machine 
with internal states 0, 1, ..., nm; the state 0 correspond to 
stopping the work. Initially in all cells we have 1, the head is 
over some cell, and the machine is in state 1. Further, we have the 
table (two-dimensional matrix; state of cell and state of
machine can be regarded as indices), and each element of this table 
contains three numbers: new state of cell, new state of machine, and
necessary movement (one cell left, no movement, or one cell right).
The work of the machine proceeds as follows: we perform stepwise in
a cycle the following procedure:
     (1) we read the state of the cell under the head;
     (2) on the basis of two numbers (the state of the cell of the tape
and the state of the machine) we found in the table new state of the
cell, new state of machine, and necessary movement. We rewrite the 
content of the cell, change the state of the machine, and perform
the prescribed movement. If new state of the machine is equal to 0,
we stop.
     As one can see, this is hardly convenient for obtaining visual 
effects. More suitable is the use of two-dimensional Turing machines,
e.g., on rectangular grid with movements up/down/left/right. 
     Presented here there are two programs: TURIREON.PAS and 
TURIDERE.PAS. The first demonstrates some fixed Turing machines.
The most beatiful are the machines which generates chaotic image 
with some elements of order or spiral with returns to the center.
The second performs recursive enumeration of Turing machines via
the tree of variants, namely, we construct empty table and begin
to simulate the Turing machine; as soon as control gets to some
cell in the table of the machine, we exhaustively enumerate
the content of this cell and recursively call the procedure
of simulation. Too trivial machines we try to throw out as 
earlier as possible. The result looks like the inhabitant of 
another planet shoots into enemies who attack him: the most part of 
the generated machines just produce movement of the head in various 
directions with linear trace behind the head. Unfortunately, nice 
machines are very rare, linear traces dominate.
     The program TURIDERE needs TP 5.0 for normal work (otherwise,
due to the necessity to use some ersatz of the Cleardevice procedure,
it works too slowly). 
     As in other cases, comments are in Russian (and often 
abbreviated). However, if somewho will write to me that he wants to 
have them translated, I shall translate.
