The Alan Turing Internet Scrapbook

Turing Machine simulation in Java

maintained by Andrew Hodges

Alan Turing home page

Scrapbook index

Short Biography

Bibliography

My Books

A Turing Machine Applet The Applet on this page has been written by Graham Stalker-Wilde grahams@pipeline.com He has generously allowed it to be used on this site, and you may download for personal use the Java source in this file. The Applet code is ©Graham Stalker-Wilde. This Applet is powerful enough to run any Turing machine with reasonable storage requirements, but at the moment it is only being used on this page to present a very particular, rather trivial Turing machine which performs unary addition. It has the effect of composing two groups of 1's placed on its tape into a single group of 1's, much the same as the machine described on pages 98-99 of my book Alan Turing: the Enigma. But this is enough to illustrate the basic features of the Turing's concept -- the atomic elements, out of which any possible computation, however complicated, can be composed. Running the machine in the Applet will illustrate these general features of Turing machines:- a finite number of possible states ("configurations" in Turing's original 1936 paper) the scanning of one square at a time moving one place to left or right for the next symbol to be scanned how this motion and the new state is determined by the single scanned symbol. Note: In this simulation, the tape moves to left or right through a fixed scanning head, rather than the head moving to right or left along the tape.

Operating the Applet The tape contains squares either blank ( - ) or marked with a 1. The scanned symbol is indicated by the symbol in square brackets. The table of states specifies the behaviour of the machine for each state, and for each possible scanned symbol. The current state is indicated by the ** asterisks. Click on STEP to see the machine operate one step. Click on RUN to see it pass through the whole sequence. Click on RESET to restore the original configuration. Sorry folks, the applet runs on Netscape but on Internet Explorer may not display the right hand part of the tape. I hope to fix this bug later.

More detailed comment on the machine: It will only work on two groups of 1's separated by a single blank. The machine is demonstrated here for the addition of 3 and 5, but the states as specified would work for input groups of any length. (The second group could be empty.) It has to start with the scanned square within the left-hand group of 1's. State 0 scans rightwards through the left-hand group, then finds and fills the blank square. State 1 scans rightwards through the right-hand group until it finds the end. State 2 erases the last 1. State 3 serves to return the scanned square to the left-hand end of the group.

A more interesting example The same Applet as you have already downloaded is used on another page to show a Turing machine testing the divisibility of one integer by another. More Java If you are interested in Java, try this Applet for factorisation which can test numbers up to 9223372036854775807.

My Main Page

Continue Scrapbook

Alan Turing Home Page

Bibliography

My Book

Last updated 27 April 2000.

I am always grateful for feedack and suggestions for new links: andrew@synth.co.uk