Turing’s World Ch8 Exercise 33

Exercise 33 (5-tuple machines)In Chapter 6, page 76, we discussed a different formalization of the notion of a Turing machine, one where a machine could both print and move in one step. Such a machine would need to have arcs labeled by triplets, not pairs, and so need five items to specify one state transition, not four. For example the 5-tuple, {3,*,_,(MOVE LEFT),4} would represent the command: in state 3 if you see a *, print a blank, move left, and go to state 4. You can always simulate any such machine with a 4-tuple machine.(a)Come up with a general technique for transforming any 5-tuple machine into a 4-tuple machine. (Assume that the machines use only the default alphabet.)(b)Apply your technique to the 5-tuple machine given by:

{0,*,*,(MOVE RIGHT),0},

{0,_,*,(MOVE RIGHT),1},

{1,*,*,(MOVE RIGHT),1},

{1,_,_,(MOVE LEFT),2},

{2,*,_,(MOVE LEFT),3},

{3,*,_,(MOVE LEFT),4},

{4,*,*,(MOVE LEFT),4},

{4,_,_,(MOVE RIGHT),5}

This machine which computes a familiar numerical function f of two arguments, is borrowed from Enderton’s chapter of [Barwise], which is based on the 5-tuple approach. Run your simulation on a few input tapes and see if you can figure out what f is. Compare the machine you have just built with the machine you built earlier to compute the same function. Which uses the most states? Compare the time-space count of the two when used to compute f(4,4) and f(8,8).

Current State Symbol Read Action Next State
0 * Write “*” 1
3 * Write “*” 4
6 * Write “_” 7
7 _ Move Left 8
1 * Move Right 0
0 _ Write “*” 2
4 * Move Right 3
8 * Write “_” 9
9 _ Move Left 10
10 * Write “*” 11
11 * Move Left 10
10 _ Write “_” 12
12 _ Move Right 13
3 _ Write “_” 5

This is simply an addition function f(k,m) = k+m.  For example given the input tape = “__***_**__”, the result tape = “__****__”.  Or in simpler terms 2+1 = 3.  Note that one * represents the number zero and two *’s represents the number one.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: