The Cover PagesThe OASIS Cover Pages: The Online Resource for Markup Language Technologies
SEARCH | ABOUT | INDEX | NEWS | CORE STANDARDS | TECHNOLOGY REPORTS | EVENTS | LIBRARY
SEARCH
Advanced Search
ABOUT
Site Map
CP RSS Channel
Contact Us
Sponsoring CP
About Our Sponsors

NEWS
Cover Stories
Articles & Papers
Press Releases

CORE STANDARDS
XML
SGML
Schemas
XSL/XSLT/XPath
XLink
XML Query
CSS
SVG

TECHNOLOGY REPORTS
XML Applications
General Apps
Government Apps
Academic Apps

EVENTS
LIBRARY
Introductions
FAQs
Bibliography
Technology and Society
Semantics
Tech Topics
Software
Related Standards
Historic
Created: March 19, 2001.
News: Cover Stories

Turing Machine Markup Language (TMML).

Robert C. Lyons of Unidex Inc. has created an XML-based Turing Machine Markup Language (TMML) for describing Turing machines. "Just for fun," he says in the XML-DEV announcement... "I created TMML and the Universal Turing Machine stylesheet to have some fun and to learn more about the XSLT language; I designed this site to share what I learned about Turing machines and XSLT. A language is Turing complete if it is powerful enough to implement any Turing machine. It is widely believed that Turing machines are powerful enough to perform any calculation that can be performed by a modern computer program." Lyons' TMML web site "provides sample TMML documents and an XSLT 1.0 stylesheet that interprets (i.e., executes) the Turing machine that is described in a TMML document. This XSLT stylesheet, which is a Universal Turning Machine, is an existence proof that XSLT 1.0 is Turing complete. The stylesheet, which is available in HTML format and as an XSLT document, has been run with SAXON and Xalan. It does not use any extension functions or proprietary features. The stylesheet does use the xsl:key instruction and the XPath key() function."

From the web site description:

A Turing machine can be thought of as a primitive, abstract computer. Alan Turing, who was a British mathematician and cryptographer, invented the Turing machine as a tool for studying the computability of mathematical functions. Turing's hypothesis (also known has Church's thesis) is a widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer program can solve. There are problems that can not be solved by a Turing machine (e.g., the halting problem); thus, these problems can not be solved by a modern computer program.

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.


Hosted By
OASIS - Organization for the Advancement of Structured Information Standards

Sponsored By

IBM Corporation
ISIS Papyrus
Microsoft Corporation
Oracle Corporation

Primeton

XML Daily Newslink
Receive daily news updates from Managing Editor, Robin Cover.

 Newsletter Subscription
 Newsletter Archives
Bottom Globe Image

Document URI: http://xml.coverpages.org/ni2001-03-19-b.html  —  Legal stuff
Robin Cover, Editor: robin@oasis-open.org