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 |
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 0 | left | ||
blank | 1 | left | ||
blank | 1 | left |
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 |
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
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.
How must the state table be modified to accomodate a Turing machine that runs a finite set of instructions? Explain.
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 down. Originally used by Roman general
Julius Caesar, the original Caesar cipher was created by shifting the
alphabet three letters down, 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’’
Fill in the table for a Caesar cipher with a shift of
A | |
B | |
C | |
D | |
E | |
F | |
G | |
H | |
I | |
J | |
K | |
L | |
M | |
N | |
O | |
P | |
Q | |
R | |
S | |
T | |
U | |
V | |
W | |
X | |
Y | |
Z |
Use a Caesar cipher with a shift of
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
The plugboard on an Enigma machine would typically use
original message: ‘‘AN APPLE A DAY KEEPS THE DOCTOR AWAY’’
encoded message:
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 ‘‘CEN’’.
Consider if the message ‘‘ROTARY CHICKEN’’ went through the rotors. What would be the encoded message?
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?
Take the message from question