A Turing Machine (TM)   for aba*       presented by   -   -   - (names are removed temporarily for the review period of a related paper )

Turing Machines (TMs) define the most powerful class of automata for processing the most complex sets, namely, the recursively enumerable sets. A TM has a finite set of states with one START state and some HALT states and an infinitely long READ/WRITE tape devided into distinct cells. The input is initially placed on the tape starting from the left most cell. The TAPE HEAD initially points to the leftmost cell. A TM for     aba*    is shown in action with an input string "abaa" . Press the START_ANIMATION button for invoking the animation. The machine starts execution from the start state. The moving short arrow shows the execution path and the colored input symbol on the tape shows the current symbol being processed.   (a, a, R)   on a transition arrow means read an a from the current tape-cell, write an a to the same cell, and move Right on the tape.

For more on TMs

A TM for   aba*    
For a PDF document on TMs,   Please click Here!

 

Any Turing Machine (TM ) can be represented in a table and then the table can be encoded into a string. The above TM is represented in Table 1 as shown below:

      

FROM TO READ WRITE MOVE
1 3 a a R 3 4 b b R 4 4 a a R 4 2 ∆ ∆ R
Table 1 The TM for aba* is represented in tabular form

In Table 1, each row represents a transition. The interpretation of the topmost row is that from state 1 to state 3, there is a transition that reads the symbol a, writes the symbol a, and moves Right . Using a method suggested by Cohen, D. (1997)[ Introduction to Computer Theory (2nd ed.), New York: John Wiley ], each transition of the TM (that is, each row of Table 1) can be coded into a string of a's and b's as shown in Table 2. In the first transition of the TM, (that is, in the top row of Table 1), state 1 is represented by one a, state 3 is represent by three a's after one b, which serves as a separator (SEP in Table 2). After that, one b serves as a separator. Then, aa stands for reading an a , and the next aa stands for writing an a, and then the 11th symbol, b, stands for moving Right.

       

FROM SEP TO SEP READ WRITE MOVE Concatenated Code
1 3 a a R a b aaa b aa aa b abaaabaaaab 3 4 b b R aaa b aaaa b ab ab b aaabaaaabababb 4 4 a a R aaaa b aaaa b aa aa b aaaabaaaabaaaab 4 2 ∆ ∆ R aaaa b aa b ba ba b aaaabaabbabab
Table 2. Each Row of Table 1 is coded in a's and b's in red color immediately below that row

In Table 2, SEP stands for separator. For READ & WRITE, an a is coded as aa, a b is coded as ab, and a ∆ is coded as ba. For MOVE, R (right), is coded as b and L (left) is coded as a. Please note that in each coded row, after the 2nd b (which is a separator), there are exactly five coded symbols. The concatenated coded string for the entire TM is:
abaaabaaaabaaabaaaabababbaaaabaaaabaaaabaaaabaabbabab

Following Cohen (1997), the first eleven symbols (abaaabaaaab) of the code represent the first transition of the TM, that is, the top row of Table 2. State 1 is represented by one a, state 3 is represent by three a's after one b, which serves as a separator. After that, one b serves as a separator (SEP). Then, aa stands for reading an a , and the next aa stands for writing an a, and then the 11th symbol, b, stands for moving Right. Similarly, each transition is translated into a string. Coded TMs are used in proving important theorems.

Thank you for visiting this page!