Date: Mar. 26, 2001
Link: http://www.unidex.com/turing/
Source Author or Organization: Bob Lyons, Unidex Inc.

Turing Machine Markup Language (TMML) is an XML application for the description of Turing machines. TMML is named for Alan Turing's hypothetical Universal Turing Machine, which demonstrated the essential idea of a modern computer a decade before it was possible to implement one electronically.

A Turing machine consists of a theoretical tape moving back and forth in front of a read/write head. The tape is comprised of adjacent boxes, and each box contains a symbol. The machine can read symbols from and write symbols to the "boxes", and perform a limited set of states and manipulation functions, such as a "halt" state and a "transition" function (which performs actions such as copying the current symbol and state to the next box). Given enough tape and logic, any computable problem can be solved.

Using TMML, the Turing machine definitions can be employed to build XML documents that are Turing Machines solving particular computation problems. The TMML site posts sample code for machines that increment a number, calculate the length of a string, and implement the ROT13 cipher. The machines operate via an Extensible Style Language Transformations (XSLT) stylesheet that "executes" the Turing machine described in TMML.

Developing the Universal Turing Machine in XSLT, which is "an existence proof that XSLT 1.0 is Turing complete", was the author's original motivating intent.

The site also offers a short introduction to Turing machines, with related links.