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.

Advertisements

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: