Turing Machine Markup Language

The Turing Machine Markup Language (TMML) is an XML language for describing Turing machines. This page describes TMML (pronounced timmel), and provides the TMML DTD and sample TMML documents (i.e., sample Turing machines expressed in TMML).

There are various definitions of the Turing machine. For example, some definitions of the Turing machine define halt states, and other definitions do not. In some definitions, the tape is infinite in both directions, and in others, the tape is only infinite to the right.

TMML was designed to be a superset of these various Turing machine definitions. The differences among these definitions are not significant; in general, a Turing machine that conforms to one definition can be easily converted into an equivalent Turing machine that conforms with another definition.

The DTD for TMML is available as HTML and as a downloadable file.

Daan Wanrooy wrote an XML schema for TMML; it's is available as HTML and as a downloadable file. Thank you Daan!

The following sample TMML documents are available in HTML format and in XML format:

  • A Turing machine that implements the ROT13 cipher. [HTML] [XML]
  • A Turing machine that verifies that a string is a palindrome. Thanks to Daan Wanrooy for writing this Turing machine! [HTML] [XML]
  • A Turing machine that increments a number. [HTML] [XML]
  • A Turing machine that calculates the length of a string. [HTML] [XML]

If you feel inspired to create a Turing machine as a TMML document and would like your TMML doc (or a link to it) featured on this web site, then please contact me at boblyons@unidex.com. If you are writing your first Turing machine, then I recommend that you try to tackle an easy problem (e.g., calculating the sum of two numbers). As much as I'd like to see an XSLT processor in TMML, you probably have better things to do with the rest of your life! :-)

Powered by Turing Machines :-)