代写COMP2K、代写Python编程设计

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

热门主题

课程名

mktg2509 csci 2600 38170 lng302 csse3010 phas3226 77938 arch1162 engn4536/engn6536 acx5903 comp151101 phl245 cse12 comp9312 stat3016/6016 phas0038 comp2140 6qqmb312 xjco3011 rest0005 ematm0051 5qqmn219 lubs5062m eee8155 cege0100 eap033 artd1109 mat246 etc3430 ecmm462 mis102 inft6800 ddes9903 comp6521 comp9517 comp3331/9331 comp4337 comp6008 comp9414 bu.231.790.81 man00150m csb352h math1041 eengm4100 isys1002 08 6057cem mktg3504 mthm036 mtrx1701 mth3241 eeee3086 cmp-7038b cmp-7000a ints4010 econ2151 infs5710 fins5516 fin3309 fins5510 gsoe9340 math2007 math2036 soee5010 mark3088 infs3605 elec9714 comp2271 ma214 comp2211 infs3604 600426 sit254 acct3091 bbt405 msin0116 com107/com113 mark5826 sit120 comp9021 eco2101 eeen40700 cs253 ece3114 ecmm447 chns3000 math377 itd102 comp9444 comp(2041|9044) econ0060 econ7230 mgt001371 ecs-323 cs6250 mgdi60012 mdia2012 comm221001 comm5000 ma1008 engl642 econ241 com333 math367 mis201 nbs-7041x meek16104 econ2003 comm1190 mbas902 comp-1027 dpst1091 comp7315 eppd1033 m06 ee3025 msci231 bb113/bbs1063 fc709 comp3425 comp9417 econ42915 cb9101 math1102e chme0017 fc307 mkt60104 5522usst litr1-uc6201.200 ee1102 cosc2803 math39512 omp9727 int2067/int5051 bsb151 mgt253 fc021 babs2202 mis2002s phya21 18-213 cege0012 mdia1002 math38032 mech5125 07 cisc102 mgx3110 cs240 11175 fin3020s eco3420 ictten622 comp9727 cpt111 de114102d mgm320h5s bafi1019 math21112 efim20036 mn-3503 fins5568 110.807 bcpm000028 info6030 bma0092 bcpm0054 math20212 ce335 cs365 cenv6141 ftec5580 math2010 ec3450 comm1170 ecmt1010 csci-ua.0480-003 econ12-200 ib3960 ectb60h3f cs247—assignment tk3163 ics3u ib3j80 comp20008 comp9334 eppd1063 acct2343 cct109 isys1055/3412 math350-real math2014 eec180 stat141b econ2101 msinm014/msing014/msing014b fit2004 comp643 bu1002 cm2030
联系我们
EMail: 99515681@qq.com
QQ: 99515681
留学生作业帮-留学生的知心伴侣!
工作时间:08:00-21:00
python代写
微信客服:codinghelp
站长地图