Describing and visualizing what a Turing Machine does

117 Views Asked by At

I'm trying to describe what the TM shown below "does" on a blank tape. I'm not really sure how to assimilate all the abstract information (states, moves, etc) into an intuitive sense of the TM's action. How would you describe its effect in case? enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

It writes a *, moves right 3 times, writes another *, then moves left and writes *'s between the two original *'s, moves left of the *'s, writes a *, moves left again, writes another *, then moves right, then moves left, and then stops. ... leaving 6 *'s' and ending in the left most *. Also note the head ends up two spaces to the left of its original start position. When it has halted, it has taken 16 steps.

In terms of tape transitions ([] indicates head position):

__[_]____

__[*]____

*[]

*[]

*[]

[]_

___[_]_

___[]*_

__*[]**

__[]**_

__[*]***_

[]****_

[*]****

[]*****

[*]*****_

[]****_

[*]*****_