Machine post

The Pesta Machine (MP) is an abstract computer proposed by Emil Leon Post (eng. Emil Leon Post ), which differs from the Turing machine in its simplicity. Both machines are algorithmically “equivalent” and were invented to clarify the concept of “algorithm”. In 1936, the American mathematician Emil Post in the article described a system that has algorithmic simplicity and is capable of determining whether a particular task is algorithmically solvable. If the task has an algorithmic solution, then it is also representable in the form of a sequence of commands for the Post machine.

Principle of operation

The Post machine consists of a carriage (or a read and write head) and an infinite tape divided into cells (see an example below). Each cell of the tape can be in 2 states - to be either empty - 0 , or labeled with a label 1 . During the cycle of operation of the machine, the carriage can move one position to the left or right, count, change the character in its current position.

The operation of a Post machine is determined by a program consisting of a finite number of lines. To operate the machine, you need to set the program and its initial state (that is, the state of the tape and the position of the carriage). The carriage is controlled by a program consisting of numbered command lines that are not necessarily ordered, if each command has a line to which to jump. It is usually assumed that if the transition is not specified in the command, the transition occurs to the next line. Each command has the following syntax:

  i K j

where i is the command number, K is the carriage action, j is the number of the next command (sending).

In total, there are six types of commands for the Post machine:

  V j - put a label, go to the j-th line of the program.
    X j - erase the label, go to the j-th line of the program.
    ← j - move to the left, go to the j-th line of the program.
    → j - move to the right, go to the j-th line of the program.
    ?  j1;  j2 - if there is no label in the cell, then go to the j1th program line, otherwise go to the j2th program line.
    !  - end of the program (stop).

In the "stop" command, the transition to the next line is not indicated.

After the startup program, options are possible:

• the work may end with an impracticable command (erasing a non-existent label or writing to the marked field);
• work can end with the Stop command;
• the work will never end.

Examples: addition and subtraction of natural numbers P, Q [

Let the natural (nonnegative integers) numbers P and Q be represented by a set of P and Q ones and be separated by zero. Let the initial position of the carriage is on the leftmost "1" group of units Q (marked with the symbol "v").

  v
  ... 00111110111000 ...
       ----- ---
         Pq

The addition of two numbers is trivial - it is enough to put 1 between them and erase one extreme right "1" from Q. The subtraction program consists of sequentially changing the leftmost "1" of the sequence "1" in the image Q and the right "1" of the sequence "1" in image P. At the beginning of the program, the carriage is set to the leftmost "1" of Q:

  1. ← - step left
 2.?  1, 3 - if the cell is empty, go to step 1, if not, go to 3
 3. 0 - remove the label
 4. → - step to the right
 five. ?  4, 6 - if the cell is empty, go to step 4, if not, go to 6
 6. 0 - remove the label
 7. → - step to the right
 eight. ?  9, 1 - if the cell is empty, go to step 9, if not, to 1
 9. !  - end

Note that the number of the transition command is not indicated if the transition occurs to the next line in order (for clarity of the text). In the 6th line, looping is possible if Q> P.

see also

Other abstract artists and formal computing systems

• Normal Markov Algorithm (Production Programming)
• Turing Machine (Automated Programming)
• Recursive function (computability theory)
• State machine
• Lambda calculus (functional programming)
• Brainfuck (imperative programming)

Abstract (ie, existing not really, but only in imagination) Post and Turing machines, designed to prove various statements about the properties of programs for them, were proposed independently of each other (and almost simultaneously) in 1936 by the American mathematician Emil Post and the English mathematician Allan Turing. These machines are universal performers that are fully deterministic, allowing to “enter” the initial data, and after running the programs “read” the result. The Post machine is less popular, although it is significantly simpler than the Turing machine. With its help, you can teach the first computer programming skills.

Abstract Post machine is an infinite tape, divided into identical cells, each of which can be either empty or filled with a label "V", and a head that can move along the tape one cell to the right or left, put a label into the ribbon cell, if This label was not there before, erase the label if it was, or check the presence of the label in the cell. Information about the tape-filled cells indicates the state of the tape, which may change during the operation of the machine. At each moment of time the head ("-") is located above one of the cells of the tape and, as they say, looks at it. Information about the location of the head along with the state of the tape characterizes the state of the Post machine, Figure 1.16.

Fig.1.16. Abstract machine Post

The Post machine command has the following structure:

n Km,

where n is the ordinal number of the command, the K-action performed by the head, t is the number of the next command to be executed.

There are only six teams of the Post machine, Fig.1.17:

Fig.1.1. Post machine commands.

Situations in which the head must put a mark where it already exists, or, conversely, erase the mark where it does not exist, are emergency (unacceptable).

The program for the Post machine will be called a non-empty list of commands, such that 1) the command with the number n in the nth place; 2) the number m of each command coincides with the number of any command in the list.

From the point of view of the properties of the algorithms studied with the help of the Post machine, the most interesting are the reasons for stopping the machine when executing the program:

1) stop at the stop command; such a stop is called effective and indicates the correctness of the algorithm (program);

2) stop when executing an invalid command; in this case, the stop is called ineffective;

3) the car never stops; in this and in the previous case we are dealing with an incorrect algorithm (program).

We will understand the initial state of the head against the empty cell to the left of the leftmost label on the tape. Consider the implementation of some typical elements of the programs of the Post machine.

1. Let the initial state of the head be set and it is required to write two labels on the empty tape: one to the section under the head, the second to the right of it. This can be done using the following program (the result of its execution is shown to the right of the command):

Fig.1.2. An example of the element of the program machine Post.

2. We show how you can use the conditional transition command to organize a cyclic process. Let the tape have a record of several marks in a row and the head is above the most extreme mark on the right. It is required to translate the head to the left to the first empty position.

The program will look like this:

The conditional branch command is one of the basic means of organizing cyclic processes, for example, to find the first label to the right (or left) of the head located above the empty cell; finding the left (or right) of the head of an empty cell, if it is located above the label, etc.

3. Let us dwell on the representation of numbers on the tape of the Post machine and the execution of operations on them.

The number k is represented on the tape of the Post machine with k + 1 tags running in a row (one label means the number “O”). Between two numbers there is an interval of at least one empty section on the tape. For example, the entry of the numbers 3 and 5 on the tape of the Post machine will look like this:

We note that the system of writing numbers used in the Post machine is nonpositional.

Create a program to add to an arbitrary number of units. Suppose that only one number is written on a tape and the head is located above one of the cells in which there is a label belonging to this number:

To solve the problem, you can move the head to the left (or right) to the first empty cell, and then apply the label.

The program that adds a label to the left to the number has the form:

The program that adds the number to the right of the number is:

(the only difference is in the direction of head movement in the first team. Check the performance of these programs on any particular examples).

Suppose that the head is located at a distance of several cells to the left of the number to which you want to add one. In this case, the program is complicated. A “number search block” will appear - two commands leading the head to the state described in the previous example:

Below are the full texts of the programs, which add a unit to the left and to the right, respectively:

In the first case, it is not necessary to move the head to the leftmost mark of the number.

4. We present a program for adding non-negative integers a and on the Post machine, when the head is over a and a, and b is to the right of a and a certain number of cells. This program implements the following algorithm: the first number is gradually moved to the second before they merge, and then one label is erased (otherwise the result would be one more than the correct one).

In the case of more complex initial conditions, when it is not known, the number to the right or left of the head (and the number of cells), the following principle can be applied: move the head to the right and left and mark the degree of head removal from the initial position, find the number and then apply the well-known addition program. At the same time, it is checked whether the head is above one of the number marks, and if so, the problem is solved. Otherwise, it is checked whether the section to the right of the head and the next one is empty; if both are empty, then the head is returned one step and a mark is put, and then the same operation is performed on the left and on the marked track the head returns to the right, etc. until the head hits a number, after which the previously discussed programs can be applied:

Post machine can be considered as a simplified computer model. In fact, both the computer and the Post machine have:

• Indivisible media (cells - bits), which can be filled or unfilled;

• a limited set of elementary actions - commands, each of which

executed in one clock (step).

Both machines work on a program basis. However, in the Post machine, the information is located linearly and is read in a row, and in a computer one can read information at the address; the set of computer commands is much wider and more expressive than the commands of the Post machine, etc.