## 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 |

2 | * | MOVE RIGHT | 3 |

3 | * | Write “*” | 4 |

5 | _ | MOVE LEFT | 6 |

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