Alan Turing gave his life in the pursuit of mathematics and computer science. Without him, we may not have won the Second World War, the modern computer might look and behave very differently and Bletchley Park might not be quite so famous.
We are learning ...
So that we can ...
 Know that Turing Machines can be viewed as a computer with a single, fixed program expressed using :
 A finite set of states in a state transition diagram with a start state and halting states
 A finite alphabet of symbols
 An infinite tape (in one direction only) marked off in squares
 A sensing readwrite head
 Represent Turing Machines using
 A tape
 A Transition function (which represents the state transition diagram)
 Be familiar with the structure of Turing Machines that perform simple computations
 Be able to handtrace simple Turing Machines
 Explain the significance of the Turing Machine and the Universal Turing Machine to the subject of computation.
Modelling computation
Modelling involves creating a simplified version of a system. If the model is too complicated, you might as well make a copy of the device. So, what are the minimal features that our computational model would need?
 Input : without it we can’t describe a problem to solve
 Processing : need some way of getting from input to output
 Storage : need to keep track of what we have done
 Output : without it we can’t get an answer to the problem
Now let’s think, in practice how we could affect these components in a real computer?
 Input : Paper tape, punch cards, keyboard, mouse, touch screen
 Processing : Finite state machine, valves, transistors, Intel i7 processor
 Storage : Paper tape, magnetic core, DDR3 RAM
 Output : Blinking lights, paper tape, visual display unit
Modelling a computer should simplify it’s operation. Make it too complicated and we’re building a computer which defeats the object of modelling one. Making models means they are not real so we can add features which are not possible in practice such as infinite memory and infinite running time. Nice!
What must our model of a machine be able to do? Follow instructions? Check. Read information from a tape? Check. Write information to a tape? Check. Move the tape? Check. In fact, allowing our model computer to do this is pretty powerful stuff (really!). Considering that this ‘information’ could represent a computer model as well this means that our model computer could model another model computer. Cool!
Activity 1 What is a 'Turing Machine'? 
In 2012, our favourite search engine, Google, release a special Doodle ...
Click to have a go at the puzzle. You can also download the puzzle from here for offline fun!
If you looked carefully at the Doodle, you will have seen all the major components of a Turing Machine  a conceptual computational model (i.e. one which was never actually designed to be built) which Alan proposed in 1936 in the paper " On Computable Numbers, with an application to the Entscheidungsproblem" (available to download from here if you should care to read it!) In essence, he tried to produce an abstract computational model to work out if the solution to Hilbert's Tenth Problem had roots that are whole numbers (like you do) using a 'human computer' with a pencil and a piece of paper!
A Turing Machine (TM) is a conceptual computational device with an infinite length of tape (1, 2 or 3 dimensional) to store data on (actually, it's only infinite to the right, but it's still infinite). The tape is split into a series of cells, like frames on a reel of film.
The machine has two alphabets, the tape alphabet which includes all symbols that can appear on the tape and an input alphabet, a proper subset of the tape alphabet, which includes symbols from the tape alphabet except for the blank symbol (a cell not yet written to). We are only allowed to specify the input to the machine using the input alphabet and hence we can't, normally, specify a blank symbol as input and have to use a delimiter symbol like a '#' to separate sections of the input, if necessary.
An example of tape and input alphabet
Some implementations also have tape symbols for head / tape movement so they can implement so called Universal Turing Machines (Turing Machines that model other Turing Machines)
The TM is controlled by a Finite State Machine (FSM) which can be described by a transition function, δ. At any time, the TM can be in one of a finite number of states (indicated by the state register) which must include a start state, in which the Turing Machine begins computation, and a set of terminal states, in which the machine will immediately stop, or accept, its input (even though there might still be symbols on the tape). The TM has a read/write head, which can read from and write individual symbols to, the tape. The read/write head can be moved along the tape, one cell at a time, in either direction.
^{1} In some implementations, it's the tape that moves, not the read/write head
^{2} Some implementations do not have the concept of 'stay put'
Task 1.1 I hope you were reading carefully ...
In the TL;DR, you will hopefully have noticed some terms in bold writing. These are, what I consider to be, the keywords for the topic of Turing Machines.
In your notebooks : Write down a list of definitions based on these keywords. You may find this hard because you've not learnt about Turing Machines yet ... try your best, you can always refine them later.
OUTCOME : List of keywords and definitions in the topic of Turing Machines 
A Turing Machine computation
There are three stages to a Turing Machine computation ...
STAGE 01 : Initialise  The data to be processed is written to the tape using the tape alphabet.
 The read/write head is positioned on the leftmost nonblank symbol on the tape.
 The Turing Machine is set in it's initial state.
STAGE 02 : Compute  The Turing Machine reads the symbol under the read/write head.
 The appropriate transition function is applied based on the symbol read and the current state of the machine.
 A symbol is written onto the tape overwriting the current symbol.
 The read/write head is moved one cell to the left or the right (or 'stays put' in some variants).
 The state of the machine is changed (although this may be a self transition so that state remains the same).
STAGE 03 : Finish  No appropriate transition function is defined (REJECT).
 The read/write head moves past the lefthand edge of the tape (REJECT).
 The terminal state is reached (ACCEPT)  there may still be unread symbols on the tape.
 The data on the tape is the machines output.
Task 1.2 Nice of you to ask!
Using a suitable application create a flowchart to represent "A Turing Machine computation".
OUTCOME : Flowchart which represents A Turing Machine Computation 
Activity 2 Practical Turing Machines 
During the next part of the topic, we will be making actual Turing Machines like these guys have ...
A Turing Machine  Overview (5:08)
Mechanical Turing Machine in Wood (4:22)
Only joking! We can program our Turing Machines in a number of different ways ...
 As State Transition Diagrams (like FSAs);
If you can't remember what a Finite State Machine is, shame on you! Not helpful, I know, so you might want to check out 'I want Moore machines!'. We can either use JFLAP or TuringKara to create the simulation.
 As Transition rules in a table;
A transition rules table is simply an alternative representation for the transition function, in tabular form.
 As a Transition Function.
The transition function basically maps the current state of the machine and it's input to an output, direction of head movement and the next state of the machine.
5tuple transition function
There will be one row in the transition function for each transition in the machine. Don't worry if you can't see how these will work at this stage  it will make sense when you've followed the worked example.
Worked Example : NOT Operation
Machine specification
Create a Turing Machine which takes a single dimensional tape as input containing a series of '1 's and '0 's right terminated by a '# '. The read/write head should be set at the leftmost nonblank symbol on the tape. The machine should read the contents of the tape from left to right and perform a logical NOT operation on the contents of the tape. When the machine reaches the terminator symbol, the machine should reset itself by moving the read/write head back to the leftmost nonblank symbol on the tape.
Input alphabet = {0 ,1 ,# } Blank symbol = Tape alphabet = {0 ,1 ,# ,}
States = {S0 ,S1 ,S2 }
Initial state = S0
Terminal state = S2
Test data
Test the machine operation with a single dimensional tape containing the string 00101# .

Step One : Create the Machine in JFLAP ...
JFLAP is quite easy to use (!) You create the FSM to control the Turing Machine much like you would create any other Finite State Machine (actually a Mealy Machine) by creating the states and then adding the transition. You 'run' the Turing Machine using 'Input > Step' from the menu and specifying the tape contents.
JFLAP Turing Machine (7:20)
Turing machine which simulates a NOT operation
Step Two : Create the Machine in TuringKara ...
It's a bit trickier creating the Turing Machine in TuringKara because you create Kara's world first and then specify the 'program' which is actually the FSA. However, TuringKara draws the FSA for you whilst you specify 'rules' for the transitions in tabular form. You 'run' the machine using the 'Play' button in the World editor.
TuringKara Turing Machine (6:37)
Click to enlarge Kara's world
Click to enlarge Kara's Programs
Step Three : Create a State Transition Table ...
To create the State Transition Table, you simply look at each state in the FSA and replicate each transition originating at that state in a separate row in the table.
Take care if you are answering examination questions that you pay particular attention to the order of the columns in the state transition table  they are often in a different order to this!
Step Four : Create a Transition Function
The Transition Function is very similar to the State Transition Table. Compare them to convince yourself! Each row in the transition function represents one of the Transition Rules in the state machine.
δ(S0,1) = (0,R,S0)
δ(S0,0) = (1,R,S0)
δ(S0,#) = (#,L,S1)
δ(S1,1) = (1,L,S1)
δ(S1,0) = (0,L,S1)
δ(S1,B) = (B,R,S2)
In this representation, 'B ' represents a blank square, 'R ' represents right and 'L ' represents left head movement.
Task 2.1 Practical Turing Machines
You should evidence what you have done through a combination of screenshots and written explanations. In all cases, the data left on the tape at the end of the computation is the Turing Machines output.
Complete the following exercises using both JFLAP and TuringKara. If you do not have them installed, either download the software using the links above or ask your teacher to provide them to you in class. For each of the following problems, you should attempt to create a Turing Machine in JFLAP and one in Turing Kara, a State Transition Table and a set of Transition Rules. Look back at the worked example if you need any guidance.
You'll be fine 'cause I've given you the FSA :)
Unary incrementer
Machine specification
Create a Turing Machine which takes a single dimensional tape as input that contains a unary number (simply a series of '1 's) terminated by a 'blank' at the right. The read/write head should start at the leftmost '1 '. The machine should read the contents of the tape from left to right and replace the first blank symbol with a '1 ', thereby incrementing the unary number. The machine should reset the read/write head to the leftmost '1 ' on the tape before terminating.
Input alphabet = {1 } Blank symbol = Tape alphabet = {1 ,}
States = {S0 ,S1 ,S2 }
Initial state = S0
Terminal state = S2
Test data
Test the machine operation with a single dimensional tape containing the string 111 . 
Binary incrementer
Machine specification
Create a Turing Machine which takes a single dimensional tape as input that contains a binary number consisting of a series of '0 's and '1 's terminated on it's right side by a blank square. The read/write head should start on the leftmost nonblank symbol. The machine should read in the digits from left to right and flip the bits as necessary in order to increment the binary number. When the read/write head detects a blank square, it should reset itself by moving the read/write head back to the leftmost nonblank symbol before terminating.
Input alphabet = {0 ,1 } Blank symbol = Tape alphabet = {0 ,1 ,}
States = {S0 ,S1 ,S2 }
Initial state = S0
Terminal state = S2
Test data
Test the machine operation with a single dimensional tape containing the string 01 . You may need to run the machine a number of times to convince yourself that it works correctly. 
OUTCOME : Four Turing Machines, implemented in JFLAP and TuringKara and tested appropriately. 
 If we conform to the standard Turing Machine formulation, the tape is finite to the left and infinite to the right and hence the read/write head should always start on the left (the finite side). However, we would normally parse binary from right to left (LSB to MSB) and hence, the implementation can look wrong.
The implementation of the tape can look back to front

In a 'practical / physical' Turing machine, it's the tape that moves through the machine whereas in most 'computational' Turing Machine models, it's the read/write head that moves and the tape that's stationary. Confused? You will be!

You could also represent the machine as a 4tuple transition function where the machine can optionally output a symbol or move the tape/head. The can simplify the operation of the Turing Machine if it needs to seek through the tape without writing to it.
4tuple transition function
 Standard Turing Machines are deterministic  there is only one possible transition from any state to another state. You can implement nondeterministic Turing Machines as well but they end up in parallel universes ...

Turing Machines can have multidimensional tape, more than one tape or more than one read/write head to reduce the complexity of the machine but, none of these variations are any more powerful (in computational terms) than a standard machine. They simply make life easier for us. Any Turing Machine can be constructed using the standard model (left bounded / right infinite single dimensional tape, single read / write head, deterministic) but it might take a little longer ...
A complex Turing Machine may have hundreds or thousands of states and a very complicated transition function. As with writing any high level language, the key to developing a complex Turing Machine is to combine simpler Turing Machines together. One Turing Machine can effectively be used as a subroutine in another Turing Machine.
All other types of computing machine are reducible to an equivalent Turing Machine. No physical computing device can be more powerful than a Turing machine. If a Turing machine cannot solve a yes / no problem (decision problem) nor can any physical computing device  the problem is not solvable. By the Power of Turing Machines! If a Turing machine DOES NOT halt on ALL possible inputs, then no effective procedure exists which can solve the algorithm. We can say that the function is NOT COMPUTABLE!
Task 2.2 More complex machines
Less help with these! You can make them in JFLAP or TuringKara (or both).
EASIEST : Unary Decrementer
Develop a Turing Machine that will decrement a Unary number given to it on a tape. The machine should simply search through the number to find the last nonblank symbol, erase it and reset itself so as to allow the computation to be executed more than once. As an extension you could try to prevent the machine from executing the computation if the tape is empty.
HARD : String copier
Develop a Turing Machine that will copy a binary number an arbitrary distance along a tape. The number will be separated from it's copy by a delimiter symbol (a '#' sign). The machine should not destroy the original symbols on the tape but can temporarily change them to track it's operation. The machine does not need to reset itself because it's done it's job when it's done it once.
HARDEST : Binary multiplier
Develop a Turing Machine that will multiply a binary number by 2 (binary shift). Essentially, this machine should be given a binary number (LSB on the left hand side) and shift the binary number to the right on the tape by one position, padding the number to the left with a '0'.
Ask your teacher for the (possible) solutions when you've had enough!
OUTCOME : Complete mastery of Turing Machines. Unlikely to ever get anything more complicated! Ever! 
Tracing machine execution
If we don't have software to trace the operation of our Turing Machine (and let's be fair, Alan didn't), we need to derive a suitable manual method of keeping track of where the Turing Machine is up to in it's computation.
Formal Turing machine tapes have a definite left end but are infinite to the right. There are two accepted methods for manually tracing the progress of the computation ...
Method A : The 'many copies of the tape and indication of the read/write head position underneath' method
In this method, we draw out multiple copies of the tape (yuk), one for the initial tape setup and one for each state change, and indicate the position of the read/write head underneath the tape using a box with the current state written in it (or sometimes to the right of the tape if we're pushed for room).
Method B : The 'write it out in an easier way which isn't as visual' method
In this method, we represent the current state of the machine simply as a string which contains details of ...  The cells to the LEFT of the read/write head
 The current STATE of the machine (i.e. the state register!)
 The cells UNDER and to the RIGHT of the read/write head
(cells to the LEFT, current STATE, cells UNDER and to the RIGHT)
Task 2.3 Manual machine execution
Download the worksheet Manual machine execution.docx, complete the print for assessment by your teacher.
OUTCOME : Completed worksheet 
Activity 3 Universal Turing Machines (UTM) 
In his 1936 Paper, 'On Computable Numbers', Alan asks ...
The essence of Turing’s UTM concept is that a description of a Turing machine (states, transition function etc.) could be written on the tape that also contains the data to be processed. The UTM would process the description of the machine, applying it to the data on the tape. The UTM is considered by many to be a precursor of the von Neumann architecture / stored program computer, i.e. that instructions and data can be stored in the same memory. The UTM can also be viewed as an interpreter.
Task 3.1 Write some notes (and draw a picture)
Just write some notes on this section. You could draw a picture of Alan if you want to, but you must choose a modern art movement to style it in. Choose from ...
 Abstract expressionism
 Art Deco
 British Popart
 Color field
 Cubism
 Dada
 Futurism
 Kinetic art
 Minimalism
 Russian Futurism
 Surrealist
 Symbolism
OUTCOME : Notes on Universal Turing Machines and awareness of how powerful they are. 
How about these?
What's next?
Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT

