Post Machine

Blog: Post Machine

INTRODUCTION

The Post-Turing Machine is a very simple type of Emil Post's Turing Machine-equivalent calculation model.

The Shipping Machine works by first reading the program, which ends as a string list, and then obtains the user input in the form of a series.

HISTORY

In 1936 he introduced the Turing Machine, and shortly thereafter Emil Leon Post (1897-1954) invented the postal machine.

They hoped it would become a “Universal Algorithm”. The condition that must be met with "such an algorithm" is that any language that can be accurately described by People, must be adopted by another version of this machine.

This can make it much more powerful than the FA or PDA.

Sr. no.	Title	Abstract	Year
1.	Finite Combinatory Processes—Formulation 1	Post's model of a computation differs from the Turing-machine model in a further "atomization" of the acts a human "computer" would perform during a computation.	1936
2.	Recursive Unsolvability of a Problem of Thue.	Atomized the Turing 5-tuples to 4-tuples: "Our quadruplets are quintuplets in the Turing development. That is, where our standard instruction orders either a printing (overprinting) or motion, left or right, Turing's standard instruction always order a printing and a motion, right, left, or none"	1947
3.	Wang model.	Reduction to only four instructions of the Wang model (Wang B-machine) as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set {write 0, write 1, move left, move right, if scanning 0 then goto instruction i, if scanning 1 then goto instruction j}.	1957
4.	Davis model (Turing–Post machine).	Davis assigns the numbers "1" to Post's "mark/slash" and "0" to the blank square. To quote Davis: "We are now ready to introduce the Turing–Post Programming Language. In this language there are seven kinds of instructions: {PRINT 1, PRINT 0, GO RIGHT, GO LEFT, GO TO STEP i IF 1 IS SCANNED, GO TO STEP i IF 0 IS SCANNED, STOP}.	1978
5.	Davis–Sigal–Weyuker's Post–Turing program model.	This model allows for the printing of multiple symbols. The model allows for B (blank) instead of S0. The tape is infinite in both directions. Either the head or the tape moves, but their definitions of RIGHT and LEFT always specify the same outcome in either case (Turing used the same convention).	1994

WHAT IS TURING MACHINE ?

The Turing Machine was invented by Alan Turing in 1936.

The Turing machine contains a tape of unlimited length at which literary work can be done. Tape contains endless cells where each cell contains an insertion mark or a special marker called blank. It also contains a header pointer that identifies the current read cell and can navigate in both directions.

EXPRESSING TURING MACHINE

A Turing Machine is presented as a 7-tuple (Q, T, B, ∑, δ, q0, F) where:
Q is a set of limitations
T is the alphabet of tape (symbols that can be written on Tape)
B is an empty symbol (all cells are filled with B except input characters)
∑ Input alphabet (symbols that are part of input characters)
Δ is a transition function that sets the map Q × T → Q × T × {L, R}.
q0 is the first condition
F a set of endpoints. If any F status is reached, the input unit is accepted.

WORKING

PM's accept some context-free languages and some non-context- free languages.

For any Turing Machine there exists a Post Machine which accepts the same language, and vice versa. The proof that for any Post Machine there exists a Turing Machine, say M, which accepts the same language, follows from the fact that the queue of the Post Machine can be represented by the leftmost part of the tape of the Turing Machine M and the operations on the queue can be simulated by operations on the tape.

A Turing machine consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1, a 0, or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells. The head is also capable of erasing symbols and writing new symbols into the cells.

OPERATIONS

There are three different tasks the Shipping Machine can complete:

O1: The machine goes into an unusable state: you must label the cell that already has the label, or delete the cell without the label. Then the execution is stopped And an ineffective suspension occurs.

O2: The machine comes to a command setting. The machine has completed the process.

O3: The machine never stops or comes to an unusable command: it goes into an endless loop.

PROPERTIES

Alphabet for input letters and special mark # (aabb #). A linear end is called a store or line containing a complete input unit (using the FIFO stack). This area can be read, which means that the left-hand character can be removed for testing.

STORE can be added as well, which means the new character can be connected to the right of anything that already exists.

Read the provinces - which removes the left-hand character from the SHOP and branch accordingly. The end of the branch on the machine occurs in READ provinces. Branch which means empty Store has been read. PMs determine, so no two edges from READ have the same label.

Add states - which concatenate a character onto the right end of the string in STORE. This is different from PDA PUSH states, which concatenate characters onto the left. Post machines have no PUSH states. No branching can take place at an ADD state.

A START and some halt states called ACCEPT or REJECT - If we are in a READ state and there is no labeled edge for the character we have read then we crash, which is equivalent to taking a labeled edge into a REJECT state. We can draw our PM's with or without REJECT states.

Example,

Post machine is deterministic. So, we do not have the edges that lead to REJECT states but instead we allow the path to crash in the READ state if there is no place for it to go. {a^n, b^n}