Turing Machines - Tutorials |
All about Turing Machines: This simple introduction
to Turing machines covers the basic concepts in a narrative form, and
has some good links at the bottom of the page that point to more
detailed information.
More programming-oriented detail about the operation of a Turing machine can be found in this excerpt for Ivars Peterson's The Mathematical Tourist. Peterson's article provides the necessary background for this article by Jack Copeland, which includes a little theory. Dr. Copeland is the Director of the Turing Archive for the History of Computing, University of Canterbury in New Zealand. Another resource which covers some of the same ground is available here. A more rigorous description of a Turing machine can be found at Wikipedia. If it's mathematical rigor you need, take a look at Wolfram's MathWorld site. Universal Turing Machines: The Universal Turing machine
is the basis of the von Neumann architecture, the principle
architecture that most CPUs use today. (The distant second award
goes to the Harvard architecture.) Of course, MathWorld also has a description.
Church-Turing thesis: In 1900, David Hilbert
proposed a series of 23 mathematical problems. The second
problem--"Prove that the axioms of arithmetic are consistent" was
partly addressed by Kurt Gödel, who showed that no proof was possible within the domain of arithmetic itself. Turing extended Gödel's work and
showed that even if something could be expressed as an algorithm, there
is no positive proof that the algorithm will be able to compute a
solution in a finite period of time. For instance, no positive
proof that an algorithm to compute the exact value of π in a
finite amount of time can be found. Hilbert's problem is callled
the "Entscheidungsproblem."
Turing's thesis: Turing machines can do anything that can be described as "rule of thumb" or "purely mechanical." Church's thesis: A function of positive integers is effectively calculable only if recursive. At first glance, it may be hard to see why these are similar statements. To see why they are, read this article first. A more comprehensive discussion of the Church-Turing thesis (and why it's hyphenated!) is here. Jack Copeland, a leading Turing scholar, wrote a very good article on the Church-Turing thesis. Halting problem: The halting problem
can be defined as: Given a finite algorithm with finite input,
can we prove if the program will run in a finite time? This was
the problem that Turing addressed. (The answer is no.)
How would anyone go about writing a program to prove or disprove the halting problem? There's a clear explanation here as to why such a program can't be written. Busy Beaver problem: The
busy beaver problem is an example of the halting problem. It only
stops when it runs out of resources such as tape or the patience of the
person running the program, neither of which are infinite. Wikipedia gives a more rigorous definition; additional articles about the busy beaver problem are here: [ 1 | 2 | 3 | 4 ].
|
Home
|
Overview
|
History
|
Tutorials
|
Multimedia and
Lectures Examples and Simulations | Advanced Topics |