s5cs49 turing machines
This page is mainly about s5cs49 turing machines
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...
Turing Machines
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 read-write 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 hand-trace 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? ✔️. Read information from a tape? ✔️. Write information to a tape? ✔️. Move the tape? ✔️. 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 and a little crazy!
Activity 1
What is a 'Turing Machine'?
In 2012, our favourite search engine, Google, release a special Doodle...
Click to have a go.
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!
Kids who read, succeed!
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.
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'
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, and should, 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 non-blank 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 left-hand 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 machine's 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.
5-tuple 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 non-blank 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 non-blank symbol on the tape.
Test data
Test the machine operation with a single dimensional tape containing the string 00101#.
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 non-blank 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 non-blank 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 relatively 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
Appearance of the tape
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)
Kara's world
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 Transition Function. 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.
Test data
Test the machine operation with a single dimensional tape containing the string 111.
Finite State Automata
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.
Finite State Automata
Unary incrementer
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 non-blank 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 non-blank symbol before terminating.
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.
Finite State Automata
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 non-blank 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 non-blank 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.
Finite State Automata
Binary incrementer
Unary adder
Machine specification
Create a Turing Machine which takes a single dimensional tape containing two unary numbers (consisting of a series of '1's) separated by a '#' symbol. The read/write head should start on the leftmost '1' in the leftmost number. The machine should read the digits from left to right until it finds the separator symbol ('#') which it should replace with a '1'. It should then continue reading through the remaining number until it reaches a blank square. It should reverse the direction of the read/write head and erase the rightmost '1' before terminating by resetting the tape head to the leftmost '1' in the single unary number.
Test data
Test machine operation with a single dimensional tape containing the string 1111#11.
Finite State Automata
Create a Turing Machine which takes a single dimensional tape containing two unary numbers (consisting of a series of '1's) separated by a '#' symbol. The read/write head should start on the leftmost '1' in the leftmost number. The machine should read the digits from left to right until it finds the separator symbol ('#') which it should replace with a '1'. It should then continue reading through the remaining number until it reaches a blank square. It should reverse the direction of the read/write head and erase the rightmost '1' before terminating by resetting the tape head to the leftmost '1' in the single unary number.
Input alphabet = {1,#}
Blank symbol =
Tape alphabet = {1,#,}
States = {S0,S1,S2,S3,S4}
Initial state = S0
Terminal state = S4
Test data
Test machine operation with a single dimensional tape containing the string 1111#11.
Finite State Automata
Unary adder
Parity calculator
Machine specification
Create a Turing Machine which takes a single dimensional tape as input containing a binary string consisting of a series of '0's and '1's. The read/write head should start on the leftmost non-blank symbol. The machine should read through the number and keep track of whether it has currently read an odd or an even number of '1' in the binary string. When the machine reached the first non-blank symbol, it should write a '1' if it has detected an odd number of '1's in the binary number or a '0' if it detects an even number of '1's in the binary number essentially enforcing even parity in the binary string. The machine should reset itself to the left most non-blank symbol before terminating.
Test data
Test machine operation with two single dimensional tapes, one containing the string 10011 and the other containing the string 10010.
Finite State Automata
Create a Turing Machine which takes a single dimensional tape as input containing a binary string consisting of a series of '0's and '1's. The read/write head should start on the leftmost non-blank symbol. The machine should read through the number and keep track of whether it has currently read an odd or an even number of '1' in the binary string. When the machine reached the first non-blank symbol, it should write a '1' if it has detected an odd number of '1's in the binary number or a '0' if it detects an even number of '1's in the binary number essentially enforcing even parity in the binary string. The machine should reset itself to the left most non-blank symbol before terminating.
Input alphabet = {0,1}
Blank symbol =
Tape alphabet = {0,1,}
States = {S0,S1,S2,S3}
Initial state = S0
Terminal state = S3
Test data
Test machine operation with two single dimensional tapes, one containing the string 10011 and the other containing the string 10010.
Finite State Automata
Parity calculator
Now print out your evidence for your notebooks.
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 4-tuple 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.
4-tuple 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 ...
Wha?
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 non-blank 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'.
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 (I couldn't think of a snappier title).
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 (yeah, I know).
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', 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.
Extension Activities - how about these?
A Python Turing Machine?
It is possible to write a simple program to simulate a Turing machine operating on a one-dimensional array to represent the tape. Choose one Turing machine that you have studied and create a 'simulator' in Python. Submit your code and evidence of the output of the machine.
(Alan) Turing Machines
Just read ...
"In the 1930's, whilst working on the concepts of computable mathematical functions, the famous mathematician Alan Turing published a paper called 'On Computable Numbers' where he discussed the operation of a 'Computer' as a definition of what the term 'computable' meant. But this was the 1930's; 20 years before computers as we know it were invented. Turing's 'computer' was actually a human mathematician. Turing supposed that, given a method or procedure, an algorithm, this mathematician could compute any mathematical function mechanically. Turing defines a function as 'computable' if it can be calculated by some mechanical means. He wondered how the 'computer' would carry out this so called procedure. How does a mathematician compute? On paper, usually, following a procedure, certainly. He writes something, looks something up, looks forward, looks back. Turing generalises that this paper / tape is structured with squares which contain symbols and the procedure would be described by a 'machine' with a finite number of states (Turing calls them m(achine)-configurations). Turing was a modest man. He didn’t use the term 'Turing Machine' or 'Universal Turing Machine' in his paper. He called them 'Automatic machines' and 'Universal Computing Machines'. It is only in recognition of his contribution to this field that we now refer to them using his name."
My mate, Tibor
With this in mind, here are two more fabulous Computerphile videos for you to watch.
Turing Machine Primer - Computerphile (5:51)
Busy Beaver Turing Machines - Computerphile (17:55)
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.
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
Last modified: March 21st, 2024
