For simulation purposes, a (basic) TM, illustrated below, consists of a semi-infinite tape (to store symbols), and a finite control with a RW head that can move to the right or to the left. The original Turing machine (TM) described by Alan Turing consists of an infinite tape, a finite control, and a read/write (RW) head positioned over the tape. Reading, Massachusetts: Addison-Wesley, 1979, Chapter 7. Introduction to Automata Theory, Languages, and Computation. NOTE: Most of the theoretical material in this chapter is from Hopcroft, J.E., and J.D. A Correction" Proceedings of the London Mathematical Society, Vol 43, 1937, pp. 230-265 and "On Computable Numbers, With an Application to the Entscheidungsproblem. "On Computable Numbers, With an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, Vol 42, 1937, pp. Turing defined a class of computing machines, and used them in an influential paper in which he showed that Hilbert’s Entscheidungsproblem (Decision Problem or Halting Problem) was unsolvable. Amsterdam: North-Holland, 1981.) Turing Machines The Lambda Calculus, Its Syntax and Semantics. During WWII, he was instrumental in cracking the German Enigma cipher. 1954) British mathematician who solved Hilbert’s Entscheidungsproblem. (The New Encyclopaedia Britannica, 1991, Vol 5, pp. Many of the problems have since been solved, and each solution was a noted event. In his address, "The Problems of Mathematics," he surveyed nearly all the mathematics of his day and endeavoured to set forth the problems he thought would be significant for mathematicians in the 20 th century. 1943) German mathematician who in 1900 enunciated a list of 23 research problems at the International Mathematical Congress in Paris. NOTE: This article is from sections of Chapter 13 "Applications in Automata Theory, Part III" of my unpublished textbook "Appplied Algorithms and Data Structures."
The code is a conversion into unmanaged C++ under Visual Studio 2010 of an old Borland C++ version that I implemented when I was teaching Automata Theory at Washington State University, Department of Electrical Engineering and Computer Science, from January 2000 to December 2002.
This article describes the implementation and testing of a simulator of a universal Turing machine.