COMP2K 图灵机器设计细节

Turing MachinesLaboratoryInstructionsCodebreaking (Part A)Recommended you complete this part by the end of Week 3. Youshould demo this lab in your Week 4 practical session.Turing Completeness (Part B)Recommended you complete this part by the end of Week 6. Youshould demo this lab in your Week 7 practical session.COMP2048 Theory of Computation S. S. Chandra1Part ACyphers andCodebreaking[This is the lab sheet for the Codebreaking Demonstration. You must demonstrate it to the instructorin one of your practical sessions BEFORE the due date in order to be awarded marks. Please checkthe ECP for the correct due date. Note that sections are ‘complete’ and marks are awarded byattempting each task AND correctly answering related questions to the satisfaction of theinstructor.]

1.The deciphering of secret messages

in World War II was one of the main drivers of the computationalage we currently live in. Cipher machines developed around this time were sophisticated enough thatbreaking 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 crackthe code generated by the German Enigma Machine and later the more general-purpose electroniccomputer called the Colossus.In the first part of the lab, we study the much simpler Caesar cipher used during Roman times that canbe broken by hand, though we shall use computers instead. In the second part, we will use a pre-builtsimulator of an Enigma code machine in Python to crack Enigma coded messages just as the Allieswould have done in World War II. Lastly, we will cover general code breaking tasks for those lookingfor a challenge.
Section I – Caesar Cipher (3 Marks)The Caesar cipher is a simple plain text substitution cipher, where you replace your message alphabetsto the same alphabet but shifted bya constant offset.-------------------------------[See the starting code provided in test_caesar.py and test_caesar_break.py]a) Use Python dictionaries to createa shifted directory of letters that will allow you to map yourletters to shifted ones, so that you can use the encrypt and decrypt code provided intest_caesar.py to encode and decode Caesar cipher messages. Demonstrate that your codeworks for your own custom message by running the encrypt and decrypt methods within the scriptprovided.b) This type of cipher is easily broken by observing that some letters in the English language occurmore often than others, such as the letter ‘e’. Use the initial code provided intest_caesar_break.py to write an algorithm to break the code and decrypt the messageprovided.c) Extend your script to break any Caesar cipher message of an arbitrary shift if you haven’t alreadydone so. Test out your code with your neighbour or mate by exchanging ciphered messages ofunknown shifts between yourselves.COMP2048 Theory of Computation S. S. Chandra2Section II – Enigma Cipher (5 Marks)The Enigma machine was acommercial electro-mechanical cipher device introduced to the publicbefore World War II for encrypting communication. It was adopted by the German military withvarious enhancements to make it more secure before the war broke out. It can be seen as the ultimateplain text cipher system that not only incorporates shifts but also permutations that change for everyletter encrypted by using a combination of rotors. You can find a detailed description of the machineand its internal workings in (Copeland, 2004) [Enigma, Section 2]. We may also find the Enigma videosin the Computation YouTube Playlist helpful.For our purposes however, all we need to know is that the machine maps a letter to another letter inour alphabet using two main mechanisms. Firstly, there are three rotors that can be chosen from a setof 5 or 7 distinct rotors. Each rotor maps an input letter to another output letter with a shiftdetermined by its rotation rate. All available rotors have different rotation rates and any combinationof three can be chosen to be used within the machine for ciphering. The result is that the input letterpasses through all three rotors to thoroughly jumble up the shifts to produce the output letter. Thestarting positions of the three rotors dictates the rotational offsets of the cipher and is called thewindow positions or key. The window positions change as the cipher is used, so that the initial windowpositions are required to decrypt messages. Lastly, there is an override mapping mechanism especiallyoutfitted for the Germany military called the plugboard. The board allows one to add additionalmappings 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 withhis 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 SSCas those are the initials of his name. He is also a cheapskate! He hasn’t even bothered to purchase theplug 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 Enigmamachinesimulator.After realising that his military forces are taking heavy losses, he decides to take the advice of hisgenerals and allows a different fixed, but hidden window positions for all further communications. Hehowever still refuses to buy the plugboard. He does decree though that all messages are to end withthe phrase “Hail Shakes!”.c) Using the known end phrase, phrases like which are called cribs, write an algorithm to breakShakes’ 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 taketo crack the code? How long did it take on your computer? How long do you thinkitwould’vetaken for a computer in the 1940s?!e) If Shakes the Horrible wasn’t so ignorant and worried about money, he would have purchasedboth the extra 2 rotors and the plugboard. How much longer would have the cracking his codetaken on your computer? An estimate as a number of tries or minutes/hours is sufficient.COMP2048 Theory of Computation S. S. Chandra3Section III – Code Breaking (2 Marks)A number ofsophisticated encryption schemes can be broken with some simple prior knowledge ofthe context in which the message was composed, but without knowing anything about the encryptionscheme or device.Crack the following message intercepted by the United States navy that was addressed to a Japanesenaval officer in 1941 to reveal its contents. It is actually doable by hand, but you may use Python aswell.Turing Completeness and the Game of Life[This is the lab sheet for the Game of Life Demonstration. You must demonstrate it to the instructorin one of your practical sessions BEFORE the due date in order to be awarded marks. Please checkthe ECP for the correct due date. Note that sections are ‘complete’ and marks are awarded byattempting each task AND correctly answering related questions to the satisfaction of theinstructor.]
The Game of Life (GoL) simulation can be thought of as a form of cellular automation originallydeveloped by John Conway. The game involves a set of cells within an × grid whose state is eitheralive or dead (i.e. 1 or 0 respectively). The grid effectively represents the ‘universe’ that will besimulated and the alive cells the life within it. The game is governed by a set of simple rules that dictatethe next state of each cell in this universe depending on its current state and the states of itsneighbours. 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 die2. Survival: A live cell that has 2-3 live neighbouring cells will remain alive3. Overpopulation: A live cell with more than 3 live neighbours will die4. Reproduction: A dead cell with exactly 3 live neighbours will become aliveThe game begins with an initial state of the universe with a pattern of live cells. The universe is evolvedby applying the above rules to each cell of the universe to determine the next iteration of thesimulation. The evolution of the universe is observed by continual computing the next iteration of theuniverse. 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 classprovided. In the following parts of the lab, you will be required to code up the algorithms related tothe 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. Seemy 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 (nottkinter or turtle, etc).
COMP2048 Theory of Computation S. S. Chandra5

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 thelab. An example test script is provided that enables the animation of the simulation. Another script isalso provided without animation for debugging purposes, especially for implementing the GoL rules.-------------------------------[See scripts conway.py, test_gameoflife_glider_simple.py andtest_gameoflife_glider.py]a) Implement the four GoL rules as mentioned above in the relevant parts of the conway.pymodule and test your simulation on the ‘blinker’ initial pattern. You may use the ‘simple’ scriptfirst to ensure your algorithm is working correctly.b) Change the initial pattern to the glider (already implemented in conway.py) and run theanimation to verify that the rules are working correctly. How can you tell your code is workingcorrectly?
c) Change the initial pattern to the glider gun (already implemented in conway.py) and run theanimation. What should you get and what is wrong? Fix the glider gun pattern so that its runscorrectly. 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 aplaintext 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 theformat as a single string (as provided by the standard Python file reader after suitably handlingcomments 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. Anexample 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 alarge simulation ( > 1024) with an appropriately large pattern (at least of the order of 4? orone that is acceptable to your demonstrator).f) Construct different patterns from the LifeWiki for the conway.py module by implementing runlength encoded (RLE) reader for the module as a insertFromRLE() member (see stubprovided) using the rle.py module provided. This member should accept a string of the patternin run length encoded form as defined by the format as a single string (as provided by the standardPython 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 previoussection to load and run the pattern.h) Given the Turing machine pattern runs within GoL, comment on whether GoL is Turingcomplete.Justify your answer by referencing the theory of Turing machines and the different componentsof the Turing machine pattern provided using this link.COMP2048 Theory of Computation S. S. Chandra6
WX:codehelp

评论

暂无评论