This problem set will cover a series of activities corresponding to the Turing Machines lesson.
This section provides practice with Turing machines and programs.
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
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 0 | left | ||
blank | 1 | left | ||
blank | 1 | left | ||
blank | 0 | left | ||
blank | 1 | left | stop state |
Answer: The output of a blank tape after following the above instructions will look like this:
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 0 | left | ||
blank | 1 | left | ||
blank | 1 | left |
Answer: Observe that the machine following the above
instructions will run endlessly. So, the output of the first
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
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | left | |||
left | ||||
left | ||||
blank | stop state | |||
left | ||||
left | ||||
blank | left | |||
left | ||||
left |
Answer: The output of the tape after following the above instructions will look like this:
It is helpful to construct a state table to summarize how the Turing machine will operate.
Create a state table for a Turing machine that will repeatedly
print the individual digits in
Answer: This is one possible state table:
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 2 | left | ||
blank | 0 | left | ||
blank | 2 | left | ||
blank | 1 | left |
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.
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.
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.
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 |
Use the original Caesar cipher to encrypt the following message:
‘‘TURING MACHINES ARE COOL’’.
Answer: Using the original Caesar cipher, we get
So, the encoded message would be ‘‘VWTKPI OCEJKPGU CTG EQQN’’.
Fill in the table for a Caesar cipher with a shift of
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
So, the message from part (a) would now be encoded as ‘‘XYVMRK QEGLMRIW EVI GSSP’’.
Use a Caesar cipher with a shift of
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.
First, there would be a set of plugboard settings. A plugboard
would have
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 |
If the plugboard connects the letters
Answer: The word ‘‘MESSAGE’’ would be encoded as ‘‘MSEEAGS’’.
The plugboard on an Enigma machine would typically use
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’’
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’’.
Consider if the message ‘‘ROTARY CHICKEN’’ went through the
rotors. What would be the encoded message?
Answer: Using the encoding scheme, we get
Hence, the encoded message would be ‘‘XRKSXI JDHJZEB’’.
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,
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
Therefore, the new encoded message is ‘‘EFPPA CPRTZG IRVFD’’.
Take the message from question
Answer: If we take the original message from question
So, the original message from
Therefore, the encroded message from question