Examples of Turing Machines

Examples of Turing Machines p.1/22

Higher level descriptions

We can give a formal description to a particular TM by specifying each of its seven components This way a TM can become cumbersome.
Note:

To avoid this we use higher level descriptions which are precise enough for the purpose of understanding

However, every higher level description is actually just a short hand for its formal counterpart.

Examples of Turing Machines p.2/22

Example 1
Describe a TM

that recognizes the language :

= "On input string

1. Sweep left to right across the tape crossing off every other 2. If in stage 1 tape contained a single , accept 3. If in stage 1 tape contained more that a single of s was odd, reject 4. Return the head to the left-hand of the tape 5. Go to stage 1"

and the number

Examples of Turing Machines p.3/22

Analysis
At each iteration, stage 1 cuts the number of s in half. If the resulting number of s is odd and greater than one, the original number could not have been a power of 2 and machine rejects If the number of is one than the original number of zeros must have been a power of 2, so machine accepts.

Rationale:

Hence, if

it means that

Examples of Turing Machines p.4/22

Formal description of


where:

 

 

 

is described in Figure 1 , ,
 


The start, accept, reject are respectively

Examples of Turing Machines p.5/22

      

     

     
   
Examples of Turing Machines p.6/22

   

State diagram of

   

   

       !   !   ! "!     

    

Notations

is denoted by an arrow that starts at , and is labeled by

, ends at , ends at , ends at , ends at

is denoted by an arrow that starts at , and is labeled by

is denoted by an arrow that starts at , and is labeled by



is denoted by an arrow that starts at , and is labeled by



Examples of Turing Machines p.7/22

On input

Example run
:

Examples of Turing Machines p.8/22

Comments
The arrow labeled


in

means

i.e., in state

with head reading ,

the machine goes to

, writes , and moves to right

The arrow labeled



in


means

moves to the right when reading a

0 without affecting the tape.

Note:

This machines begins by writing a blank over the leftmost zero. This allows it to nd the left-end of the tape in stage 4 It also allows only, in stage 2 to identify the case when tape contains one zero


Examples of Turing Machines p.9/22

Example 2


is the TM that decides

the language

 

 

 

is described in Figure 2 ,



Start, accept, and reject states are respectively

Examples of Turing Machines p.10/22

High-level description of
= "On input :

1. Scan the input tape to be sure that it contains a single reject

. If not,

2. Zig-zag across the tape to corresponding positions on either side of to check whether these positions contain the same symbol. If they do not, reject. Cross off the symbols as they are checked 3. When all symbols to the left of have been crossed off, check for the remaining symbols to the right of . If any symbol remain, reject; otherwise accept"

Note:

High-level descriptions of TM-s are also called implementation descriptions.

Examples of Turing Machines p.11/22

  

 

   

 

  

 

Turing machine

Figure 2:

 

  

    

 

       

    

   

State diagram for TM

 


Examples of Turing Machines p.12/22

More notations
Transitions in states and means that machines moves to the right as long as 0 or 1 is on the tape.

The machine starts by writing a blank symbol to delimit the left-hand edge of the tape Stage 1 is implemented by states through : , , if the rst symbol of input is , and if the rst input symbol was .

To simplify the gure we dont show the reject state or transitions going to reject state. These transitions occur implicitly whenever a state lacks an outgoing transition for a particular symbol. Example, on # is such a transition using different states for input starting with 1 and 0 allows

Note:

to

implement the matching operation

Examples of Turing Machines p.13/22

Note
The transition diagram in Figure 2 is rather complex. One can understand better what happens from the high-level description than from Figure 2. Therefore further we will replace transition diagrams by high-level descriptions, as initially suggested

Examples of Turing Machines p.14/22

Example 3
is a Turing machine that performs some elementary arithmetic. It decides the language


="On input string

 

1. Scan the input from left to right to be sure that it is a member of ; reject if it is not

2. Return the head at the left-hand end of the tape 3. Cross off an and scan to the right until a occurs. Shuttle between the s and s crossing off one of each until all s are gone. If all s have been crossed of and some s remain reject.

4. Restores the crossed off s and repeat stage 3 if there is another to cross off. If all s are crossed off, determine whether all s Examples of Turing Machines p.15/22 are crossed off. If yes accept, otherwise reject."

Analyzing

In stage 1 operates as a nite automaton; no writing is necessary as the head moves from left to right:

3.

2.

1.

Examples of Turing Machines p.16/22

Stage 2 nding the left-hand end

Mark the left-hand end by writing a before the input (this have been seen before) Note that if the machine tries to move the head to the left of the left-hand end of the tape the head remains in the same place. This feature can be made "the left-hand end detector" by:
1. Write a special symbol over the current position, while recording the symbol that it replaced in the control


2. Attempt to move to the left. If the head is still over the special symbol, the leftward move did not succeed, and the head must have been at the left-hand end. If the head is over a different symbol, some symbols are to the left of that position Examples of Turing Machines p.17/22

Note
Stage 3 and stage 4 of implementations have straightforward


Examples of Turing Machines p.18/22

Element distinctness problem

Given a list of strings over separated by determine if all strings are different. A TM that solves this problem accepts the language

Examples of Turing Machines p.19/22

Example 4

is the TM that solves the element distinctness problem works by comparing with , then by comparing with , and so on
 



Examples of Turing Machines p.20/22

Informal description
="On input :

1. Place a mark on top of the leftmost tape symbol. If that symbol was a blank, accept. If that symbol was a continue with the next stage. Otherwise reject. 2. Scan right to the next and place a second mark on top of it. If no is encountered before a blank symbol, only was present, so accept.

3. By zig-zagging, compare the two strings to the right of the marked -s. If they are equal, reject

4. Move the rightmost of the two marks to the next symbol to the right. If no symbol is encountered before a blank symbol, move the leftmost mark to the next to its right and the rightmost mark mark, all to the after that. If no is available for the rightmost Examples of Turing Machines p.21/22

Marking tape symbols

In stage two the machine places a mark above a symbol, in this case. In the actual implementation the machine has two different symbols, alphabet

and

in the tape

Thus, when machine places a mark above symbol it actually writes the marked symbol of at that location Removing the mark means write the symbol at the location where the marked symbol was.
 

Examples of Turing Machines p.22/22