## Turing’s World Ch8 Exercise 17

Chapter 8 Exercise 17 (Coding) In Chapter 3, page 56, we described a way to encrypt the alphabet A,B,_ with the alphabet *,_. Build a Turing machine to carry out this encryption, one that takes an arbitrary string of A’s, B’s and _’s and replaces it with the encrypted version. Assume that the input string is enclosed in parentheses, and likewise have the output delimited with parentheses. (What problems would come up if we didn’t assume this?) Your machine should start and stop on the left parenthesis. |

In the table below, for the column “Symbol Read”, the symbol “…” means any symbol not explicitly defined elsewhere as a “Symbol Read” value for the same “Current State”. For example state 2 has a transition defined for reading the symbol “)”. So “…” means anything else, which for the Turing machine below consists of the other symbols in this machine’s limited input alphabet of {”A”,”B”,”_”,”(”, “)”}, i.e. {”B”,”_”,”(”,”)”}.

Current State | Symbol Read | Action | Next State |

1 | A | Write “(” | 2 |

1 | B | Write “(” | 3 |

1 | _ | Write “(” | 4 |

7 | _ | MOVE RIGHT | 1 |

2 | ) | MOVE RIGHT | 8 |

2 | … | MOVE RIGHT | 2 |

3 | ) | MOVE RIGHT | 5 |

4 | ) | MOVE RIGHT | 6 |

4 | … | MOVE RIGHT | 4 |

3 | … | MOVE RIGHT | 3 |

15 | ) | MOVE RIGHT | 16 |

15 | … | MOVE RIGHT | 15 |

16 | _ | Write “)” | 17 |

17 | ) | MOVE LEFT | 18 |

18 | … | MOVE LEFT | 18 |

18 | ( | Write “_” | 7 |

0 | ( | MOVE RIGHT | 15 |

8 | ) | Write “_” | 9 |

8 | … | MOVE RIGHT | 8 |

9 | _ | Write “*” | 12 |

13 | _ | Write “)” | 14 |

14 | ) | MOVE LEFT | 18 |

12 | * | MOVE RIGHT | 10 |

10 | _ | MOVE RIGHT | 13 |

1 | ) | Write “(” | 19 |

5 | … | MOVE RIGHT | 5 |

5 | ) | Write “_” | 20 |

20 | _ | MOVE RIGHT | 11 |

6 | … | MOVE RIGHT | 6 |

6 | ) | Write “_” | 22 |

22 | _ | MOVE RIGHT | 23 |

23 | _ | MOVE RIGHT | 13 |

11 | _ | Write “*” | 24 |

24 | * | MOVE RIGHT | 13 |

From pg 56 of Turing’s World 3.0, an Introduction to Computability Theory by Jon Barwise and John Etchemendy:

Coding with the default alphabetOne of the many things that Turing showed in his original paper was that any symbolic computation could be simulated by one that uses only two symbols, say blank and *. This is very surprising at first glance, but it is also very important. It allows us to store information with the basic “on” and “off” that electricity provides and that digital computers run on.Turing’s idea was simple enough. Just think of it as a problem in cryptography. Find a way to encrypt words written in a large alphabet into one with just two symbols. For example, how would you encrypt A,B,_ using just *,_? One natural way that works out pretty well in practice is to use the following code:“_” encrypted by “__”“A” encrypted by “*_” “B” encrypted by “_*”Thus for example, the string ABBA_AB would be encrypted by “*__*_**___*__*”. This result explains why so much theoretical work assumes that one is dealing with an alphabet containing just two symbols. But in the actual design of Turing machines, restricting to two symbols is impractical. For this reason, Turing’s World lets you build machines using quite a few symbols. In Exercises 17-20, Chapter 8, we will explore techniques for encrypting larger alphabets using the default alphabet. |

## Leave a Reply