代做WCOMP2K Turing Machines

Turing Machines
Laboratory
Instructions
Codebreaking (Part A)
Recommended you complete this part by the end of Week 3. You
should demo this lab in your Week 4 practical session.
Turing Completeness (Part B)
Recommended you complete this part by the end of Week 6. You
should demo this lab in your Week 7 practical session.
COMP2048 Theory of Computation S. S. Chandra
1
Part A
Cyphers and Codebreaking

[This is the lab sheet for the Codebreaking Demonstration. You must demonstrate it to the instructor
in one of your practical sessions BEFORE the due date in order to be awarded marks. Please check
the ECP for the correct due date. Note that sections are ‘complete’ and marks are awarded by
attempting each task AND correctly answering related questions to the satisfaction of the
instructor.]
The deciphering of secret messages in World War II was one of the main drivers of the computational
age we currently live in. Cipher machines developed around this time were sophisticated enough that
breaking the coding system by hand was no longer feasible.
This lab was designed to allow you to follow in Alan Turing’s footsteps as he tackled such problems,
helping building one of the world’s first computational machines, the Bombe machine used to crack
the code generated by the German Enigma Machine and later the more general-purpose electronic
computer called the Colossus.
In the first part of the lab, we study the much simpler Caesar cipher used during Roman times that can
be broken by hand, though we shall use computers instead. In the second part, we will use a pre-built
simulator of an Enigma code machine in Python to crack Enigma coded messages just as the Allies
would have done in World War II. Lastly, we will cover general code breaking tasks for those looking
for a challenge.
Section I – Caesar Cipher (3 Marks)
The Caesar cipher is a simple plain text substitution cipher, where you replace your message alphabets
to the same alphabet but shifted by a constant offset.
-------------------------------
[See the starting code provided in test_caesar.py and test_caesar_break.py]
a) Use Python dictionaries to create a shifted directory of letters that will allow you to map your
letters to shifted ones, so that you can use the encrypt and decrypt code provided in
test_caesar.py to encode and decode Caesar cipher messages. Demonstrate that your code
works for your own custom message by running the encrypt and decrypt methods within the script
provided.
b) This type of cipher is easily broken by observing that some letters in the English language occur
more often than others, such as the letter ‘e’. Use the initial code provided in
test_caesar_break.py to write an algorithm to break the code and decrypt the message
provided.
c) Extend your script to break any Caesar cipher message of an arbitrary shift if you haven’t already
done so. Test out your code with your neighbour or mate by exchanging ciphered messages of
unknown shifts between yourselves.

COMP2048 Theory of Computation S. S. Chandra
2

Section II – Enigma Cipher (5 Marks)
The Enigma machine was a commercial electro-mechanical cipher device introduced to the public
before World War II for encrypting communication. It was adopted by the German military with
various enhancements to make it more secure before the war broke out. It can be seen as the ultimate
plain text cipher system that not only incorporates shifts but also permutations that change for every
letter encrypted by using a combination of rotors. You can find a detailed description of the machine
and its internal workings in (Copeland, 2004) [Enigma, Section 2]. We may also find the Enigma videos
in the Computation YouTube Playlist helpful.
For our purposes however, all we need to know is that the machine maps a letter to another letter in
our alphabet using two main mechanisms. Firstly, there are three rotors that can be chosen from a set
of 5 or 7 distinct rotors. Each rotor maps an input letter to another output letter with a shift
determined by its rotation rate. All available rotors have different rotation rates and any combination
of three can be chosen to be used within the machine for ciphering. The result is that the input letter
passes through all three rotors to thoroughly jumble up the shifts to produce the output letter. The
starting positions of the three rotors dictates the rotational offsets of the cipher and is called the
window positions or key. The window positions change as the cipher is used, so that the initial window
positions are required to decrypt messages. Lastly, there is an override mapping mechanism especially
outfitted for the Germany military called the plugboard. The board allows one to add additional
mappings of individual letters to other letters even before the rotors are applied.
-------------------------------
[See the starting code provided in test_enigma_simple.py and test_enigma_break.py]
Shakes the Horrible has decided to purchase a set of Enigma machines to ensure communication with
his armed forces (consisting mainly of Spider Monkeys) is secure as possible.
a) Demonstrate a working Enigma machine with the given simple example script.
In his arrogance however, he has decided to force his military to always use the window positions SSC
as those are the initials of his name. He is also a cheapskate! He hasn’t even bothered to purchase the
plug board or any additional rotors, meaning he only has access to rotors I, II and II.
b) Decipher Shakes’ message to his military given in the example script using the Enigma machine
simulator.
After realising that his military forces are taking heavy losses, he decides to take the advice of his
generals and allows a different fixed, but hidden window positions for all further communications. He
however still refuses to buy the plugboard. He does decree though that all messages are to end with
the phrase “Hail Shakes!”.
c) Using the known end phrase, phrases like which are called cribs, write an algorithm to break
Shakes’ new code into the provided script and decrypt the message provided.
d) Add a counter to your script to keep track of the number of tries. How many attempts does it take
to crack the code? How long did it take on your computer? How long do you think it would’ve
taken for a computer in the 1940s?!
e) If Shakes the Horrible wasn’t so ignorant and worried about money, he would have purchased
both the extra 2 rotors and the plugboard. How much longer would have the cracking his code
taken on your computer? An estimate as a number of tries or minutes/hours is sufficient.
COMP2048 Theory of Computation S. S. Chandra
3
Section III – Code Breaking (2 Marks)
A number of sophisticated encryption schemes can be broken with some simple prior knowledge of
the context in which the message was composed, but without knowing anything about the encryption
scheme or device.
Crack the following message intercepted by the United States navy that was addressed to a Japanese
naval officer in 1941 to reveal its contents. It is actually doable by hand, but you may use Python as
well.
-------------------------------
19 17 17 19 14 20 23 18 19 8 12 16 19 8 3 21 8 25 18 14 18 6 3 18 8 15 18 22 18 11

References
Copeland, B.J., 2004. Essential Turing: Classic Writings on Minds and Computers. Oxford University
Press, Oxford, UK.

End of Part 1 of 2
Laboratory continues next page ….

COMP2048 Theory of Computation S. S. Chandra
4

Part B
Turing Completeness and the Game of Life
[This is the lab sheet for the Game of Life Demonstration. You must demonstrate it to the instructor
in one of your practical sessions BEFORE the due date in order to be awarded marks. Please check
the ECP for the correct due date. Note that sections are ‘complete’ and marks are awarded by
attempting each task AND correctly answering related questions to the satisfaction of the
instructor.]
The Game of Life (GoL) simulation can be thought of as a form of cellular automation originally
developed by John Conway. The game involves a set of cells within an × grid whose state is either
alive or dead (i.e. 1 or 0 respectively). The grid effectively represents the ‘universe’ that will be
simulated and the alive cells the life within it. The game is governed by a set of simple rules that dictate
the next state of each cell in this universe depending on its current state and the states of its
neighbours. The rules of GoL depend on the 8-connected neighbours of a cell as follows:
1. Underpopulation: A live cell that has < 2 live neighbouring cells will die
2. Survival: A live cell that has 2-3 live neighbouring cells will remain alive
3. Overpopulation: A live cell with more than 3 live neighbours will die
4. Reproduction: A dead cell with exactly 3 live neighbours will become alive
The game begins with an initial state of the universe with a pattern of live cells. The universe is evolved
by applying the above rules to each cell of the universe to determine the next iteration of the
simulation. The evolution of the universe is observed by continual computing the next iteration of the
universe. See chapter 7, section 7.6.4 of (Moore and Mertens, 2011) for more theoretical details.
In this laboratory, you will create a simulation of the GoL using Python based on an initial class
provided. In the following parts of the lab, you will be required to code up the algorithms related to
the computation, importation and evaluation of the GoL.

Important Notes
For this practical you will need to install/already have numpy, scipy and matplotlib on your machine.
Use either Anaconda Python or WinPython to have these setup for you quickly and hassle free. See
my video series on setting up Python environments on Windows for help.
For this practical, we will only accept solutions in Python and all animations must be in matplotlib (not
tkinter or turtle, etc).
COMP2048 Theory of Computation S. S. Chandra
5

Section I – Game of Life Simulation (4 Marks)
An initial class called “conway.py” is provided with the necessary hooks required for this part of the
lab. An example test script is provided that enables the animation of the simulation. Another script is
also provided without animation for debugging purposes, especially for implementing the GoL rules.
-------------------------------
[See scripts conway.py, test_gameoflife_glider_simple.py and
test_gameoflife_glider.py]
a) Implement the four GoL rules as mentioned above in the relevant parts of the conway.py
module and test your simulation on the ‘blinker’ initial pattern. You may use the ‘simple’ script
first to ensure your algorithm is working correctly.
b) Change the initial pattern to the glider (already implemented in conway.py) and run the
animation to verify that the rules are working correctly. How can you tell your code is working
correctly?
c) Change the initial pattern to the glider gun (already implemented in conway.py) and run the
animation. What should you get and what is wrong? Fix the glider gun pattern so that its runs
correctly. Hint: One of the lines for the glider gun member is incorrectly alive.
d) Construct different patterns from the LifeWiki for the conway.py module by implementing a
plaintext reader for the module as a insertFromPlainText() member (see stub provided).
This member should accept a string of the pattern in human readable form as defined by the
format as a single string (as provided by the standard Python file reader after suitably handling
comments etc.). Demonstrate multiple initial patterns that are greater than 20x20 in size.

Section II – Turing Completeness of the Game of Life Simulation (6 Marks)
An initial class called “rle.py” is provided with the necessary hooks required for this part of the lab. An
example test script is provided that enables the running of the relevant patterns.
-------------------------------
[See scripts conway.py, rle.py and test_gameoflife_turing.py]
e) Implement a fast method for computing the weights for the rules based on convolution and run a
large simulation ( > 1024) with an appropriately large pattern (at least of the order of 4? or
one that is acceptable to your demonstrator).
f) Construct different patterns from the LifeWiki for the conway.py module by implementing run
length encoded (RLE) reader for the module as a insertFromRLE() member (see stub
provided) using the rle.py module provided. This member should accept a string of the pattern
in run length encoded form as defined by the format as a single string (as provided by the standard
Python file reader). Demonstrate multiple initial patterns that are greater than 20x20 in size.
g) Demonstrate a running GoL Turing Machine pattern by using your RLE reader from the previous
section to load and run the pattern.
h) Given the Turing machine pattern runs within GoL, comment on whether GoL is Turing complete.
Justify your answer by referencing the theory of Turing machines and the different components
of the Turing machine pattern provided using this link.

COMP2048 Theory of Computation S. S. Chandra
6

Interesting Links
Shakes’ Windows Deep Learning Python Setup Series
https://www.youtube.com/playlist?list=PLC0kkV5axv-X4OpBHlIPlIz15XNNGd3OE
Video of an 8-bit Programmable computer in GoL!
https://www.youtube.com/watch?v=8unMqSp0bFY
Various GoL and Langton’s Ant videos on the course Computation YouTube Playlist
https://www.youtube.com/playlist?list=PLC0kkV5axv-X3JOXeHGoedTMCXGakoYmt

References
Moore, C., Mertens, S., 2011. The Nature Of Computation. Oxford University Press.
End of Part 2 of 2