The Lyons Family Website

Universal Turing Machine in XSLT

This page is organized as follows:

Introduction
This page describes an XSLT 1.0 stylesheet that executes (i.e., interprets) the Turing machine that is described in the source TMML document. Thus, this stylesheet is a Universal Turing Machine and is an existence proof that XSLT 1.0 is Turing complete. A language is Turing complete if it is powerful enough to implement any Turing machine. It's widely believed that Turing machines are powerful enough to perform any calculation that can be performed by a modern computer program.

Obtaining the Universal Turing Machine Stylesheet
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; thus, you can not use James Clark's XT to execute the stylesheet.

Running the Universal Turing Machine Stylesheet
The following Instant SAXON command will invoke the utm.xsl stylesheet, in order to execute a Turing machine that adds one to the number specified on the tape. The Turing machine is described by the TMML document named "add_one_tm.xml". The input tape for the Turing machine is "199".

         saxon add_one_tm.xml utm.xsl tape=199

The output of this command includes information about each step performed by the Turing machine and the final tape, which will contain the number "200".

Description of the Universal Turing Machine Stylesheet
The Universal Turing Machine stylesheet runs the Turing machine that is specified by the source document. The source document, which specifies a Turing machine, is an XML document that conforms to the Turing Machine Markup Language (TMML). This stylesheet validates the source document using XPath expressions (rather than using the DTD for TMML).

The tape for the Turing machine is specified via the global parameter named "tape". Each character in the string represents a symbol on the tape. The tape must contain at least one symbol. Each of the symbols on the tape must be either the blank symbol or one of the symbols defined in the symbols element of the TMML source document.

In theory, the tape for the Turing machine is infinite in both directions (i.e., both to the left and to the right). The stylesheet represents the tape as a string. The stylesheet will append the blank symbol to the right end of the tape when the tape head of the Turing machine moves to the right of the last symbol on the tape. Likewise, the stylesheet will insert a blank symbol at the beginning of the tape when the tape head of the Turing machine moves to the left of the leftmost symbol on the tape.

By default, the tape head of the Turing machine is initially positioned over the first symbol on the tape (i.e., the first character of the value of the 'tape' parameter). You can specify a different initial position for the tape head via the optional global parameter named 'start_position'. The value of the 'start_position' parameter should be the character position of the symbol over which you want the tape head to be positioned initially. If you want the tape head to be initially positioned over the 2nd symbol on the tape, then set the 'start_position' parameter to 2. The default value for the 'start_position' parameter is 1.

The Turing machine will crash if the transition function is not defined for the current state and the current symbol.

The Turing machine will stop when it transitions to one of the halt states.

The Turing machine's procedure for processing the input tape is as follows:

When the Turing machine begins operation, the current state is the start state.
The Turing machine reads the tape symbol that is under the Turing machine's tape head. This symbol is referred to as the current symbol. When the Turing machine begins operation, the tape head is positioned over the symbol whose character position is specified by the 'start_position' parameter. The default value of the 'start_position' parameter is 1.
The Turing machine uses the transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.
The Turing machine changes its state to the next state, which was returned by the transition function.
The Turing machine overwrites the current symbol on the tape with the next symbol, which was returned by the transition function.
The Turing machine moves its tape head one symbol to the left or to the right, or does not move the tape head, depending on the value of the 'movement' attribute that is returned by the transition function. If the Turing machine moves the tape head to the right of the rightmost symbol, then a blank symbol is appended to the end of the tape and this new blank symbol becomes the current symbol. If the Turing machine moves the tape head to the left of the leftmost symbol, then a blank symbol is inserted at the beginning of the tape and this new blank symbol becomes the current symbol.
If the Turing machine's state is a halt state, then the Turing machine halts. Otherwise, repeat sub-step #2.

The stylesheet will display information about each iteration of the Turing machine's operation. This information includes a snapshot of the tape and a pointer (i.e., "^") under the current symbol. The pointer represents the tape head.