Презентация на тему Kinds of algorithmic systems

solvable and unsolvable problems.
4. Markov system.

to one of 6 types.

1. To mark the active

cell (to write down 1 in it) and to pass to the execution of the ith instruction.

2. To erase the mark of the active cell (to write down 0 in it) and to pass to the execution of the jth instruction.

3. To move an active cell to one step to the right and to pass to the execution of the ith instruction.

the one step to the left and to pass

to the execution of the ith instruction.

5. If an active cell is marked (there is 1 in it), then to pass to the execution of the jth instruction, otherwise you should pass to the execution of the ith instruction.

6. Stop and the end of the algorithm’s work.

execution of directions (instructions) of algorithm function of Post’s

machine.
Machine is stopped if and only when the last instruction, done by the machine, is the instruction of the 6th type and the result of its work is the word q, which is written on the tape and which is called the final one.

are equivalent to the Post algorithms, coincides with the

class of all partial recursive functions.

tape , which is divided into cells, one next

to the other. Each cell contains a symbol from some finite alphabet. Every sell is used for the record of only one symbol, which can be looked about by the head.
– The head that can read and write symbols on the tape and move the tape to the left and to the right only to one cell.

only when it is impossible to use any command

of its program.

The result of Turing machine work after its stop is the word, which is written on the tape.