Grade 7/8 Turing Machine

Turing Machines

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 \(10\) squares. The machine in both part (a) and part (b) will start in state \(a\).

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
State Scanned Symbol Print Move Tape Next State

\(a\) blank 0 left \(c\)

\(b\) blank 1 left \(a\)

\(c\) blank 1 left \(b\)

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

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

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\)

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 \(2021\).
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.

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.

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 \(5\). Use this cipher to encode the message from part (a).

A \(\phantom{..}\)

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 \(-1\) to encode your name. (Hint: Try creating a table like the ones above if you need help)

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 \(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

If the plugboard connects the letters \(E\) and \(S\), what would the word ‘‘MESSAGE’’ be encoded as?
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:

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 \(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?

A	\(\phantom{..}\)
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