Post Machines

  A particular "universal computing machine" is intended to be made to run any "algorithm", people were thinking about if such a machine exists, we can precisely define the concept of what "algorithm" is, and even more, finding "algorithm" for a particular problem automatically so that there will be no mathematical computations are required to be done by human, they're desiring a machine that can understand any langauge that can be precisely defined such as natural langauges, e.g. English, which makes it more powerful than ever that it can recognize every possible well-defined langauge.

A Post machine, denoted PM, is a collection of:

  1. The alphabet \Sigma+\lbrace \# \rbrace
  2. A linear storage called \tt STORE or \tt QUEUE, which initially contains the input string, new characters can be added to the right and the leftmost character can be removed
  3. The store alphabet \Gamma
  4. The \tt READ state that will remove the leftmost character and branching the machine to another state, read operations can read every possible characters in \Sigma\cup\Gamma, \Lambda branching is allowed and means that an empty store was read. the PMs are deterministic, so there will be no nondeterministic edges
  5. The \tt ADD state that will concatenate any character from \Sigma\cup\Gamma onto the right of the \tt STORE
  6. The set of states S where the q_0\in S will be non-reenterable start state, and some halts states(accept or reject) H\sub S

If we're in read state and read a character that non of the outgoing edges is labeled with, the machine crashes, which is equivalent to taking a labeled edge into a \tt REJECT state, so we can draw PM without \tt REJECT states. The store does not have to be empty when a string is accepted.

The Post machines look like PDAs but Post machine can accepts non-context-free langauges such as a^nb^na^n

We cannot deduce that "PMs are more powerful than PDAs" from far as we know because this example just shows that there exist at least one PM to accept one non-context-free languages.

Turing Equivalence

Any language that can be accepted by a PM can be accepted by some TMs


  Let P be a PM with input string s, we put s on the turing machine's \tt TAPE, and insert a \Delta at the leftmost position(the insertion algorithm can be done by a TM, but the algorithm here is omitted intentionally for saving space, it is simple, move all the characeters one cell right then replace the cell that are to be inserted), so that we can know when do we hit the start of the input string, then, for every \tt ADD state that adds character y, create

And for every \tt READ state with outgoing edge that labeled with x

If there're multiple outgoing edges, add them as the q_3 outgoing edges with corresponding character(in this case is x), the \Delta is still a valid label, if what left on the P's store is an empty string, we need to draw a \Delta outgoing edge in the TM

and leave the start and halt states intact.

If {a,b,c,d,e}\subset\Gamma of a TM T, we use (a,b,c,d,e;=,L) denoting instruction sequence:


and same for (a,b,c,d,e;=,R)

For the next step, we provided two subprograms for PM, the first can add a character at the back of the PM, and the second can read a character from the front of the PM, these two subprograms do the opposite things as the \tt ADD and \tt READ states do in the rules, after we created these two subprogram, we'll have the ability to add or remove character on the either end of the store. The implementation is by using a marker and the cyclic shift, the first subprogram first adds a marker \text{\textdollar} and the desired character to the end of the content of the store, then repeadedly read'n'remove the first letter of the string then add the letter to the end of the string until we've removed the \text{\textdollar}, now the originally last character, which is the one we added to the end of the string, becomes the front-most one. For the second subprogram, we do things that are basically similar to the previous one: adds a \text{\textdollar} to the end of the string, then remove'n'read, each time we read a character we turn to a specific state that can represent that character, if we ever encountered a \text{\textdollar}, we just need to take action corresponding to the state we are because that state is like somehow memorized the character that is previously read'n'removed, then we add that character to the front then read it(this time we use the normal read):

The first subprogram, names \texttt{ADD FRONT}

For the second subprogram, we need to introduce a subprogram named \texttt{SHIFT-RIGHT CYCLICALLY} that do the first-half of the algorithm: add marker, shift the content, add the last character to the front:

then we read the character which is the last one originally that we've just add:

Any langauge accepted by a TM can be accepted by some PM


  Before the construction steps, there is one thing needs to be concern: in the constructed PM, the character \Delta will be permitted to put on the store, just think that this symbol stands for blank in TMs but it is a meaningful character in PMs.
  The algorithm is TRULY elegant, beautiful and so genius, first, the TM can alter the character at any cell, while the PM can only alter character at the either end(where by "alter", we mean a simplification of "read front and add front" or "read end and add end"), which means we need to find a way to move the cell that the TM's tape head is currently at to the one end of the store of PM, we do this by using a marker \# to simulate the TM's tape head on PM, we put what was originally at the right of the tape head(including the cell that the tape currently at) to the left of \#, and the left of to the right, so now the cell that tape head currently at will becomes the first cell in PM's store, for example, if the turing machine's tape is X_1X_2X_3\underline{X_4}X_5X_6X_7X_8, now the PM's store becomes X_4X_5X_6X_7X_8\#X_1X_2X_3, if we alter the X_4 to Y which will makes the tape becomes X_1X_2X_3Y\underline{X_5}X_6X_7X_8 and move the tape head right on the TM, it will be equivalent to \tt READ\Rightarrow ADD\text{ Y} on the PM, the PM will result in X_5X_6X_7X_8\#X_1X_2Y where the first character X_5 is still the character that tape head points to, and the left-right consistency is still maintained.
  If we want to alter X_4 to Y and move the tape head left, we need to instruct the PM to \tt READ\Rightarrow\texttt{ADD FRONT}\Rightarrow\texttt{SHIFT-RIGHT CYCLICALLY}; the TM's tape will be like X_1X_2\underline{X_3}YX_5X_6X_7X_8 after operation, and what is left in the PM's store will be like Y\underline{X_3}YX_5X_6X_7X_8\#X_1X_2. However, there are two other considerations. First one is, if the tape head is pointing to the first cell, then the move left operation will causing a crash, but if it will just ends up with something like \#X_1X_2... on the PM's store which means the tape head is reading nothing but will not crash, to fix this, we add an alter operation right after the opration above is finished: try to read a letter from the front, if the letter is \#, we go to reject state, otherwise we add it back to the front. The second one is, if the tape head is pointing to the last non-blank cell in TM, and is instructed to move right, the corresponding string in the store will again be like \#X_1X_2, in this circumstance, we need to insert a \Delta right before the \# on the store, to compromise with the TM
  Before we start the PM, we need to following the convention on the TM, which is let the tape head points to the first cell, so it is obvious that we need to put the \# at the end of the string on the string of the PM, we can do this by a \tt ADD\ \# state just after the start state of the PM.
  The last thing is that the start state's reentrance on the TM, if we do the same on the PM, it will end up with two \#, so we need to use the first \tt READ state in PM as the start state in TM

Any language that can be accepted by a PM can be accepted by some TMs
Any langauge that can be accepted by a TM can be accepted by some PMs

We have:

Turing Machine=Post Machine