June 24, 2007
June 24, 2007
June 27, 2007
12.148.1 - 12.148.8
A Turing Machine for the 21st Century Christopher R. Carroll Director of Undergraduate Engineering Associate Professor and Assistant Head Electrical and Computer Engineering, 271 MWAH University of Minnesota Duluth 55812-3009
The Turing Machine, originally proposed in 1936, is a primitive model which nevertheless embodies concepts that form foundations for modern computer design.1 Described in this paper is an implementation of a Turing Machine core that is useful as a vehicle for teaching finite state machines. It is adaptable to many levels of state machine design, from introductory digital circuit implementations with gates and flip-flops through industrial Programmable Logic Controllers (PLCs) to advanced designs using Programmable Logic Devices (PLDs) and other high-end components. The Turing Machine excels as a vehicle for learning finite state machine design due to its simple structure and easily-understood operation. The particular Turing Machine core described here is especially useful due to the visible display of the machine operation produced on a standard oscilloscope to portray how the user’s design works.
A basic Turing Machine consists of a theoretically infinite tape on which information is stored in cells, and a head that moves back and forth across the tape reading and modifying information found there. By controlling the head movement and what it writes to the cells in response to information present on the tape, various computing tasks can be demonstrated.
In the Turing Machine core described here, there are two parallel tapes each holding sixteen cells. In each cell is stored one of four symbols (О, I, ―, or •) for use in the computation. The single head reads information at corresponding cells on both tapes, writes updated information to both cells, and then moves either left or right along the tapes, in response to instructions from the controlling state machine.
The unique characteristic of this design is the display produced on a standard oscilloscope to record operation of the Turing Machine. The oscilloscope display shows the contents of the two tapes as two parallel strings of sixteen symbols each, chosen from О, I, ―, or •, with one of those symbols in each string raised on the screen to indicate the head position. The display is similar to that produced by other instruments designed by the author and reported in earlier ASEE papers.2,3 As the Turing Machine operates, the head position moves back and forth, and the tape contents are updated as controlled by the state machine being used.
Carroll, C. (2007, June), A Turing Machine For The 21 St Century Paper presented at 2007 Annual Conference & Exposition, Honolulu, Hawaii. https://peer.asee.org/1888
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2007 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015