This problem set will cover a series of activities corresponding to the Turing Machines lesson.

Turing Machines

This section provides practice with Turing machines and programs.

1. Use the following instruction table to determine what the output of a blank tape would look like. If the machine runs endlessly, simply determine the output of the first \(10\) squares. The machine in both part (a) and part (b) will start in state \(a\).

   1. State	Scanned Symbol	Print	Move Tape	Next State
      \(a\)	blank	0	left	\(b\)
      \(b\)	blank	1	left	\(c\)
      \(c\)	blank	1	left	\(d\)
      \(d\)	blank	0	left	\(e\)
      \(e\)	blank	1	left	stop state

      Answer: The output of a blank tape after following the above instructions will look like this:

      

   2. State	Scanned Symbol	Print	Move Tape	Next State
      \(a\)	blank	0	left	\(c\)
      \(b\)	blank	1	left	\(a\)
      \(c\)	blank	1	left	\(b\)

      Answer: Observe that the machine following the above instructions will run endlessly. So, the output of the first \(10\) square of a blank tape will look like this:

      

2. A Turing machine is given a tape with the sequence ‘‘10110111’’. What would be the output of the tape after conducting the following instructions starting from the first \(1\)?

   State	Scanned Symbol	Print	Move Tape	Next State
   \(a\)	blank	\(0\)	left	\(b\)
   	\(0\)	\(1\)	left	\(b\)
   	\(1\)		left	\(a\)
   \(b\)	blank	\(1\)		stop state
   	\(0\)	\(1\)	left	\(b\)
   	\(1\)	\(0\)	left	\(c\)
   \(c\)	blank		left	\(c\)
   	\(0\)	\(1\)	left	\(b\)
   	\(1\)	\(1\)	left	\(a\)

   Answer: The output of the tape after following the above instructions will look like this:

   

3. It is helpful to construct a state table to summarize how the Turing machine will operate.

   1. Create a state table for a Turing machine that will repeatedly print the individual digits in \(2021\).
      

      Answer: This is one possible state table:

      State	Scanned Symbol	Print	Move Tape	Next State
      \(a\)	blank	2	left	\(b\)
      \(b\)	blank	0	left	\(c\)
      \(c\)	blank	2	left	\(d\)
      \(d\)	blank	1	left	\(a\)

   2. State tables can help identify an infinite set of instructions from a finite set. Is this program an infinite example or a finite example? Explain how you know.

      Answer: This is an example of a program running an infinite set of instructions. As we can see from the state table, the machine never enters a stop state and hence, will run continuously.

   3. How must the state table be modified to accomodate a Turing machine that runs a finite set of instructions? Explain.

      Answer: A Turing machine that runs a finite set of instructions must transition to a stop state at some point. So, the state table must be modified to include a set of instructions where the machine changes to a stop state at the end.

Cracking the Enigma Code

Enigma is the famous cipher machine used by the German military to encrypt messages during World War II. This section will explore some of the mechanics behind the machine.

4. An Enigma machine utilizes a straightforward method of encoding messages called substitution encryption. The simplest example of such a cipher is the Caesar cipher produced by shifting the alphabet some units to the right. Originally used by Roman general Julius Caesar, the original Caesar cipher was created by shifting the alphabet three letters to the right, as shown below.
   

   A	C
   B	D
   C	E
   D	F
   E	G
   F	H
   G	I
   H	J
   I	K
   J	L
   K	M
   L	N
   M	O
   N	P
   O	Q
   P	R
   Q	S
   R	T
   S	U
   T	V
   U	W
   V	X
   W	Y
   X	Z
   Y	A
   Z	B

   1. Use the original Caesar cipher to encrypt the following message: ‘‘TURING MACHINES ARE COOL’’.
      

      Answer: Using the original Caesar cipher, we get

      \(\begin{align*} \text{T} &\rightarrow \text{V}\\ \text{U} &\rightarrow \text{W}\\ \text{R} & \rightarrow \text{T}\\ \text{I} & \rightarrow \text{K}\\ \text{N} & \rightarrow \text{P}\\ \text{G} & \rightarrow \text{I}\\\\ \text{M} &\rightarrow \text{O}\\ \text{A} &\rightarrow \text{C}\\ \text{C}& \rightarrow \text{E}\\ \text{H}&\rightarrow \text{J}\\ \text{I}&\rightarrow \text{K}\\ \text{N}&\rightarrow \text{P}\\ \text{E} & \rightarrow \text{G}\\ \text{S}& \rightarrow \text{U}\\\\ \text{A} &\rightarrow \text{C}\\ \text{R} &\rightarrow \text{T}\\ \text{E} &\rightarrow \text{G}\\\\ \text{C} &\rightarrow \text{E}\\ \text{O} &\rightarrow \text{Q}\\ \text{O} &\rightarrow \text{Q}\\ \text{L} &\rightarrow \text{N} \end{align*}\)

      So, the encoded message would be ‘‘VWTKPI OCEJKPGU CTG EQQN’’.

   2. Fill in the table for a Caesar cipher with a shift of \(5\). Use this cipher to encode the message from part (a).
      

      Answer:

      A	E
      B	F
      C	G
      D	H
      E	I
      F	J
      G	K
      H	L
      I	M
      J	N
      K	O
      L	P
      M	Q
      N	R
      O	S
      P	T
      Q	U
      R	V
      S	W
      T	X
      U	Y
      V	Z
      W	A
      X	B
      Y	C
      Z	D

      Now, using this new Caesar cipher, we get

      \(\begin{align*} \text{T} &\rightarrow \text{X}\\ \text{U} &\rightarrow \text{Y}\\ \text{R} & \rightarrow \text{V}\\ \text{I} & \rightarrow \text{M}\\ \text{N} & \rightarrow \text{R}\\ \text{G} & \rightarrow \text{K}\\\\ \text{M} &\rightarrow \text{Q}\\ \text{A} &\rightarrow \text{E}\\ \text{C}& \rightarrow \text{G}\\ \text{H}&\rightarrow \text{L}\\ \text{I}&\rightarrow \text{M}\\ \text{N}&\rightarrow \text{R}\\ \text{E} & \rightarrow \text{I}\\ \text{S}& \rightarrow \text{W}\\\\ \text{A} &\rightarrow \text{E}\\ \text{R} &\rightarrow \text{V}\\ \text{E} &\rightarrow \text{I}\\\\ \text{C} &\rightarrow \text{G}\\ \text{O} &\rightarrow \text{S}\\ \text{O} &\rightarrow \text{S}\\ \text{L} &\rightarrow \text{P} \end{align*}\)

      So, the message from part (a) would now be encoded as ‘‘XYVMRK QEGLMRIW EVI GSSP’’.

   3. Use a Caesar cipher with a shift of \(-1\) to encode your name. (Hint: Try creating a table like the ones above if you need help)

      Answer: Individual answers will vary.

Enigma machines are made up of several parts: a keyboard, a lamp board, rotors, a plugboard, and internal electronic circuitry. This leads their encryption to be much more complex than a simple Caesar cipher.

5. First, there would be a set of plugboard settings. A plugboard would have \(26\) slots, one for each letter of the alphabet, and wires with two ends could plugged into these slots. So, each plug wire can connect two letters to be a pair and these letters would swap over. For example, if ‘‘A’’ is connected to ‘‘Z’’, ‘‘A’’ would become ‘‘Z’’ and ‘‘Z’’. Using this rule, the word ‘‘ZEBRA’’ would be encoded as ‘‘AEBRZ’’. Combining it with more levels of substitution encryption, our simple Caesar cipher with a shift of \(3\) would now look like this:
   

   Z	C
   B	D
   C	E
   D	F
   E	G
   F	H
   G	I
   H	J
   I	K
   J	L
   K	M
   L	N
   M	O
   N	P
   O	Q
   P	R
   Q	S
   R	T
   S	U
   T	V
   U	W
   V	X
   W	Y
   X	Z
   Y	A
   A	B

   1. If the plugboard connects the letters \(E\) and \(S\), what would the word ‘‘MESSAGE’’ be encoded as?

      Answer: The word ‘‘MESSAGE’’ would be encoded as ‘‘MSEEAGS’’.

   2. The plugboard on an Enigma machine would typically use \(5\) separate wires to create \(5\) pairs of letters that would switch. If the plugboard settings connected the letters A & L, P & R, T & D, B & W, and K & F, then what would the following message be encoded?
      original message: ‘‘AN APPLE A DAY KEEPS THE DOCTOR AWAY’’
      encoded message:

      Answer:

      encoded message: ‘‘LN LRRAE L TLY FEERS DHE TOCDOP LBLY’’

      First, replace all the As with Ls and vice versa: ‘‘LN LPPAE L DLY KEEPS THE DOCTOR LWLY’’
      Then, replace all the Ps with Rs and vice versa: ‘‘LN LRRAE L DLY KEERS THE DOCTOP LWLY’’
      Next, replace all the Ts with Ds and vice versa: ‘‘LN LRRAE L TLY KEERS DHE TOCDOP LWLY’’
      Now, replace the W with a B: ‘‘LN LRRAE L TLY KEERS DHE TOCDOP LBLY’’
      Finally, replace the K with an F: ‘‘LN LRRAE L TLY FEERS DHE TOCDOP LBLY’’

6. Then, the machines used three rotors at a time to encode a message. Each rotor provided a different encoding scheme. So, if the initial position of the alphabet looks like:

   A	G
   B	E
   C	T
   D	N
   E	D
   F	H
   G	Q
   H	Z
   I	U
   J	P
   K	B
   L	R
   M	C
   N	O
   O	X
   P	M
   Q	K
   R	Y
   S	A
   T	W
   U	F
   V	I
   W	L
   X	S
   Y	V
   Z	J

    
   Here’s how it would look after the first turn:

   A	J
   B	G
   C	E
   D	T
   E	N
   F	D
   G	H
   H	Q
   I	Z
   J	U
   K	P
   L	B
   M	R
   N	C
   O	O
   P	X
   Q	M
   R	K
   S	Y
   T	A
   U	W
   V	F
   W	I
   X	L
   Y	S
   Z	V

    
   Here’s how it would look after the second turn:

   A	V
   B	J
   C	G
   D	E
   E	T
   F	N
   G	D
   H	H
   I	Q
   J	Z
   K	U
   L	P
   M	B
   N	R
   O	C
   P	O
   Q	X
   R	M
   S	K
   T	Y
   U	A
   V	W
   W	F
   X	I
   Y	L
   Z	S

    
   Here’s how it would look after the third turn:

   A	S
   B	V
   C	J
   D	G
   E	E
   F	T
   G	N
   H	D
   I	H
   J	Q
   K	Z
   L	U
   M	P
   N	B
   O	R
   P	C
   Q	O
   R	X
   S	M
   T	K
   U	Y
   V	A
   W	W
   X	F
   Y	I
   Z	L

    
   For example, if the word ‘‘PEN’’ went through the rotors above, the resulting encoded word would be ‘‘CEB’’.

   1. Consider if the message ‘‘ROTARY CHICKEN’’ went through the rotors. What would be the encoded message?
      

      Answer: Using the encoding scheme, we get

      \(\begin{align*} \text{R} &\rightarrow \text{X}\\ \text{O} &\rightarrow \text{R}\\ \text{T} &\rightarrow \text{K}\\ \text{A} &\rightarrow \text{S}\\ \text{R} &\rightarrow \text{X}\\ \text{Y} &\rightarrow \text{I}\\\\ \text{C}&\rightarrow \text{J}\\ \text{H}&\rightarrow \text{D}\\ \text{C}&\rightarrow \text{J}\\ \text{I}&\rightarrow \text{H}\\ \text{K}&\rightarrow \text{Z}\\ \text{E}&\rightarrow \text{E}\\ \text{N} &\rightarrow \text{B}\\ \end{align*}\)

      Hence, the encoded message would be ‘‘XRKSXI JDHJZEB’’.

   2. Steven writes the message ‘‘DSCCI MCXHBN VXESZ’’ using the alphabet legend for the encoding scheme after the third turn. What was his original message? If he uses another set of three rotors to change up the encoding scheme, what would be the new message?
      

      Answer: If we use the alphabet legend, we can decrypt Steven’s message. So,

      \(\begin{align*} \text{D} &\rightarrow \text{H}\\ \text{S} &\rightarrow \text{A}\\ \text{C} &\rightarrow \text{P}\\ \text{C} &\rightarrow \text{P}\\ \text{I} &\rightarrow \text{Y}\\\\ \text{M}&\rightarrow \text{S}\\ \text{C}&\rightarrow \text{P}\\ \text{X}&\rightarrow \text{R}\\ \text{H}&\rightarrow \text{I}\\ \text{B}&\rightarrow \text{N}\\ \text{N} &\rightarrow \text{G}\\\\ \text{V} &\rightarrow \text{B}\\ \text{X} &\rightarrow \text{R}\\ \text{E} &\rightarrow \text{E}\\ \text{S} &\rightarrow \text{A}\\ \text{Z} &\rightarrow \text{K}\\ \end{align*}\)

      Therefore, his original message was ‘‘HAPPY SPRING BREAK’’. If he uses another set of three rotors to change up the encoding scheme, the alphabet legend will look like this after the first turn:

      A	L
      B	S
      C	V
      D	J
      E	G
      F	E
      G	T
      H	N
      I	D
      J	H
      K	Q
      L	Z
      M	U
      N	P
      O	B
      P	R
      Q	C
      R	O
      S	X
      T	M
      U	K
      V	Y
      W	A
      X	W
      Y	F
      Z	I

      Here’s how it would look after the second turn:

      A	I
      B	L
      C	S
      D	V
      E	J
      F	G
      G	E
      H	T
      I	N
      J	D
      K	H
      L	Q
      M	Z
      N	U
      O	P
      P	B
      Q	R
      R	C
      S	O
      T	X
      U	M
      V	K
      W	Y
      X	A
      Y	W
      Z	F

      Here’s how it would look after the third turn:

      A	F
      B	I
      C	L
      D	S
      E	V
      F	J
      G	G
      H	E
      I	T
      J	N
      K	D
      L	H
      M	Q
      N	Z
      O	U
      P	P
      Q	B
      R	R
      S	C
      T	O
      U	X
      V	M
      W	K
      X	Y
      Y	A
      Z	W

      Now using this encoding scheme to encrypt his original message, we get

      \(\begin{array}{c c c} \text{H} &\rightarrow \text{E}\\ \text{A} &\rightarrow \text{F}\\ \text{P} &\rightarrow \text{P}\\ \text{P} &\rightarrow \text{P}\\ \text{Y} &\rightarrow \text{A}\\\\ \text{S}&\rightarrow \text{C}\\ \text{P}&\rightarrow \text{P}\\ \text{R}&\rightarrow \text{R}\\ \text{I}&\rightarrow \text{T}\\ \text{N}&\rightarrow \text{Z}\\ \text{G}&\rightarrow \text{G}\\\\ \text{B} &\rightarrow \text{I}\\ \text{R} &\rightarrow \text{R}\\ \text{E} &\rightarrow \text{V}\\ \text{A} &\rightarrow \text{F}\\ \text{K} &\rightarrow \text{D}\\ \end{array}\)

      Therefore, the new encoded message is ‘‘EFPPA CPRTZG IRVFD’’.

   3. Take the message from question \(5.\)(b). What would be the original message after it has gone through the above encoding scheme? What would the encoded message be after it goes through the encoding scheme?
      

      Answer: If we take the original message from question \(5.\)(b), ‘‘AN APPLE A DAY KEEPS THE DOCTOR AWAY’’, and apply the encoding scheme, then we get

      \(\begin{align*} \text{A} &\rightarrow \text{S}\\ \text{N} &\rightarrow \text{B}\\\\ \text{A}&\rightarrow \text{S}\\ \text{P}&\rightarrow \text{C}\\ \text{P}&\rightarrow \text{C}\\ \text{L}&\rightarrow \text{U}\\ \text{E} &\rightarrow \text{E}\\\\ \text{A} &\rightarrow \text{S}\\\\ \text{D}&\rightarrow \text{G}\\ \text{A} &\rightarrow \text{S}\\ \text{Y} &\rightarrow \text{I}\\\\ \text{K}&\rightarrow \text{Z}\\ \text{E} &\rightarrow \text{E}\\ \text{E} &\rightarrow \text{E}\\ \text{P}&\rightarrow \text{C}\\ \text{S}&\rightarrow \text{M}\\\\ \text{T} &\rightarrow \text{K}\\ \text{H} &\rightarrow \text{D}\\ \text{E} &\rightarrow \text{E}\\\\ \text{D}&\rightarrow \text{G}\\ \text{O} &\rightarrow \text{R}\\ \text{C}&\rightarrow \text{J}\\ \text{T} &\rightarrow \text{K}\\ \text{O} &\rightarrow \text{R}\\ \text{R} &\rightarrow \text{X}\\\\ \text{A} &\rightarrow \text{S}\\ \text{W} &\rightarrow \text{W}\\ \text{A} &\rightarrow \text{S}\\ \text{Y} &\rightarrow \text{I}\\\\ \end{align*}\)

      So, the original message from \(5.\) (b) is encoded as ‘‘SB SCCUE S GSI ZEECM KDE GRJKRX SWSI’’. Now, we take the encoded message from question \(5.\) (b), ‘‘LN LRRAE L TLY FEERS DHE TOCDOP LBLY’’, and apply the encoding scheme. Then, we get

      \(\begin{align*} \text{L} &\rightarrow \text{U}\\ \text{N} &\rightarrow \text{B}\\\\ \text{L} &\rightarrow \text{U}\\ \text{R}&\rightarrow \text{X}\\ \text{R}&\rightarrow \text{X}\\ \text{A}&\rightarrow \text{S}\\ \text{E}&\rightarrow \text{E}\\\\ \text{L} &\rightarrow \text{U}\\\\ \text{T}&\rightarrow \text{G}\\ \text{L}&\rightarrow \text{U}\\ \text{Y}&\rightarrow \text{I}\\\\ \text{F} &\rightarrow \text{T}\\ \text{E}&\rightarrow \text{E}\\ \text{E}&\rightarrow \text{E}\\ \text{R}&\rightarrow \text{X}\\ \text{S}&\rightarrow \text{M}\\ \\ \text{D} &\rightarrow \text{G}\\ \text{H}&\rightarrow \text{D}\\ \text{E}&\rightarrow \text{E}\\\\ \text{T}&\rightarrow \text{K}\\ \text{O}&\rightarrow \text{R}\\ \text{C}&\rightarrow \text{J}\\ \text{D}&\rightarrow \text{G}\\ \text{O}&\rightarrow \text{R}\\ \text{P}&\rightarrow \text{C}\\\\ \text{L} &\rightarrow \text{U}\\ \text{B}&\rightarrow \text{V}\\ \text{L}&\rightarrow \text{U}\\ \text{Y}&\rightarrow \text{I}\\ \end{align*}\)

      Therefore, the encroded message from question \(5.\) (b) is encrypted as ‘‘UB UXXSE U GUI TEEXM GDE KRJGRC UVUI.’’.