# Universal Turing Machine
# from http://www.unidex.com/turing/utm.htm
from Xml.Xslt import test_harness
source_1 = """<?xml version="1.0"?>
<turing-machine version="0.1">
<!-- This Turing machine (TM) adds one to a whole number.
For example, if the initial tape is "199", then
the final tape will be "200".
The Turing machine assumes that the first (i.e.,
leftmost) symbol on the tape is the leftmost digit
in the number.
If the input tape is completely blank, then the final
tape will be "1". So, if the input tape is " 43",
then the Turing machine will assume that tape does not
contain a number.
This Turing Machine Markup Language (TMML) document complies
with the DTD for TMML, which is available at
http://www.unidex.com/turing/tmml.dtd.
This Turing machine can be executed by an XSLT stylesheet that is
available at http://www.unidex.com/turing/utm.xsl. This stylesheet
is a Universal Turing Machine.
The following Instant Saxon command will execute the Turing machine
described by this TMML document using the utm.xsl stylesheet:
saxon add_one_tm.xml utm.xsl tape=199
This TMML document is available at
http://www.unidex.com/turing/add_one_tm.xml.
Developed by Bob Lyons of Unidex, Inc.
Please email any comments about this TMML document to
boblyons@unidex.com.
-->
<!-- COPYRIGHT NOTICE and LICENSE.
Copyright (c) 2001 Unidex, Inc. All rights reserved.
Unidex, Inc. grants you permission to copy, modify, distribute,
and/or use the TMML document provided that you agree to the
following conditions:
1. You must include this COPYRIGHT NOTICE and LICENSE
in all copies or substantial portions of the TMML document.
2. The TMML document is licensed to the user on an "AS IS" basis.
Unidex Inc. makes no warranties, either express or implied,
with respect to the TMML document including but not limited to any
warranty of merchantability or fitness for any particular
purpose. Unidex Inc. does not warrant that the operation
of the TMML document will be uninterrupted or error-free,
or that defects in the TMML document will be corrected.
You the user are solely responsible for determining the
appropriateness of the TMML document for your use and accept
full responsibility for all risks associated with its use.
Unidex Inc. is not and will not be liable for any
direct, indirect, special, incidental or other damages
of any kind (including loss of profits or interruption of business)
however caused even if Unidex Inc. has been advised of the
possibility of such damages.
-->
<!-- The symbols are "0" through "9".
-->
<symbols>0123456789</symbols>
<states>
<!-- In the go_right state, the Turing machine moves the
tape head to the blank symbol to the right of the
number.
-->
<state start="yes">go_right</state>
<!-- In the increment state, the Turing machine keeps moving
left and changing 9's to 0's until it finds a digit
other than "9" or a blank symbol. When it finds a digit
other than "9" (or a blank symbol, which it treats as
the digit "0"), it increments the digit (e.g., replaces
"3" with "4").
-->
<state>increment</state>
<state halt="yes">stop</state>
</states>
<!-- The transition function for the TM.
-->
<transition-function>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="0"/>
<to next-state="go_right" next-symbol="0" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="1"/>
<to next-state="go_right" next-symbol="1" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="2"/>
<to next-state="go_right" next-symbol="2" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="3"/>
<to next-state="go_right" next-symbol="3" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="4"/>
<to next-state="go_right" next-symbol="4" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="5"/>
<to next-state="go_right" next-symbol="5" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="6"/>
<to next-state="go_right" next-symbol="6" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="7"/>
<to next-state="go_right" next-symbol="7" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="8"/>
<to next-state="go_right" next-symbol="8" movement="right"/>
</mapping>
<mapping>
<!-- Move to the right of the number. -->
<from current-state="go_right" current-symbol="9"/>
<to next-state="go_right" next-symbol="9" movement="right"/>
</mapping>
<mapping>
<!-- Found the blank that follows the number.
Change to the increment state and start moving left. -->
<from current-state="go_right" current-symbol=" "/>
<to next-state="increment" next-symbol=" " movement="left"/>
</mapping>
<mapping>
<!-- Change the 9 to a 0 and move left. -->
<from current-state="increment" current-symbol="9"/>
<to next-state="increment" next-symbol="0" movement="left"/>
</mapping>
<mapping>
<!-- Change the 0 to a 1. We're done. -->
<from current-state="increment" current-symbol="0"/>
<to next-state="stop" next-symbol="1" movement="left"/>
</mapping>
<mapping>
<!-- Change the blank to a 1. We're done. -->
<from current-state="increment" current-symbol=" "/>
<to next-state="stop" next-symbol="1" movement="none"/>
</mapping>
<mapping>
<!-- Change the 1 to a 2. We're done. -->
<from current-state="increment" current-symbol="1"/>
<to next-state="stop" next-symbol="2" movement="left"/>
</mapping>
<mapping>
<!-- Change the 2 to a 3. We're done. -->
<from current-state="increment" current-symbol="2"/>
<to next-state="stop" next-symbol="3" movement="left"/>
</mapping>
<mapping>
<!-- Change the 3 to a 4. We're done. -->
<from current-state="increment" current-symbol="3"/>
<to next-state="stop" next-symbol="4" movement="left"/>
</mapping>
<mapping>
<!-- Change the 4 to a 5. We're done. -->
<from current-state="increment" current-symbol="4"/>
<to next-state="stop" next-symbol="5" movement="left"/>
</mapping>
<mapping>
<!-- Change the 5 to a 6. We're done. -->
<from current-state="increment" current-symbol="5"/>
<to next-state="stop" next-symbol="6" movement="left"/>
</mapping>
<mapping>
<!-- Change the 6 to a 7. We're done. -->
<from current-state="increment" current-symbol="6"/>
<to next-state="stop" next-symbol="7" movement="left"/>
</mapping>
<mapping>
<!-- Change the 7 to a 8. We're done. -->
<from current-state="increment" current-symbol="7"/>
<to next-state="stop" next-symbol="8" movement="left"/>
</mapping>
<mapping>
<!-- Change the 8 to a 9. We're done. -->
<from current-state="increment" current-symbol="8"/>
<to next-state="stop" next-symbol="9" movement="left"/>
</mapping>
</transition-function>
</turing-machine>"""
sty_1 = """<?xml version="1.0"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:output method="text"/>
<!--
This XSLT stylesheet runs the Turing machine (TM) that is
specified by the source document. The initial tape for the
Turing machine is specified by a global parameter named 'tape'.
(Thus, this XSLT stylesheet is a Universal Turing Machine.)
The source document, which specifies a Turing machine,
is an XML document that conforms to the
Turing Machine Markup Language (TMML). The DTD for TMML
is available at http://www.unidex.com/turing/tmml.dtd.
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.
The following Instant SAXON command will invoke the
utm.xsl stylesheet, in order to execute the 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 will include the final name
which will contain the number "200".
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:
1. When the Turing machine begins operation, the current
state is the start state.
2. 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.
3. The Turing machine (TM) 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 TM crashes.
4. The Turing machine changes its state to the next state,
which was returned by the transition function.
5. The Turing machine overwrites the current symbol on the
tape with the next symbol, which was returned by the
transition function.
6. 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 TM 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 TM 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.
7. If the Turing machine's state is a halt state, then the
TM halts. Otherwise, repeat substep #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.
The American Mathematical Society provides an overview of
Turing machines at http://www.ams.org/new-in-math/cover/turing.html.
This stylesheet is available at http://www.unidex.com/turing/utm.xsl.
Developed by Bob Lyons of Unidex, Inc.
Please email any comments about this stylesheet to
boblyons@unidex.com.
-->
<!-- COPYRIGHT NOTICE and LICENSE.
Copyright (c) 2001 Unidex, Inc. All rights reserved.
Unidex, Inc. grants you permission to copy, modify, distribute,
and/or use the stylesheet provided that you agree to the
following conditions:
1. You must include this COPYRIGHT NOTICE and LICENSE
in all copies or substantial portions of the stylesheet.
2. The stylesheet is licensed to the user on an "AS IS" basis.
Unidex Inc. makes no warranties, either express or implied,
with respect to the stylesheet including but not limited to any
warranty of merchantability or fitness for any particular
purpose. Unidex Inc. does not warrant that the operation
of the stylesheet will be uninterrupted or error-free,
or that defects in the stylesheet will be corrected.
You the user are solely responsible for determining the
appropriateness of the stylesheet for your use and accept
full responsibility for all risks associated with its use.
Unidex Inc. is not and will not be liable for any
direct, indirect, special, incidental or other damages
of any kind (including loss of profits or interruption of business)
however caused even if Unidex Inc. has been advised of the
possibility of such damages.
-->
<!-- Global parameters. -->
<xsl:param name="tape" />
<xsl:param name="start_position" select="'1'" />
<!-- Global variables. -->
<xsl:variable name="symbols" select="/turing-machine/symbols" />
<xsl:variable name="blank_symbol" >
<xsl:choose>
<xsl:when test="string( /turing-machine/symbols/@blank-symbol ) != '' ">
<xsl:value-of select="/turing-machine/symbols/@blank-symbol" />
</xsl:when>
<xsl:otherwise>
<xsl:text> </xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<!-- Keys. -->
<xsl:key name="state" match="/turing-machine/states/state" use="text()"/>
<xsl:key name="mapping" match="/turing-machine/transition-function/mapping"
use="concat( from/@current-state, ' ', from/@current-symbol )"/>
<!-- Templates. -->
<xsl:template match="/">
<xsl:variable name="tm_errors">
<xsl:call-template name="validate_tm"/>
</xsl:variable>
<xsl:variable name="tape_errors">
<xsl:if test="$tm_errors = '' ">
<xsl:call-template name="validate_tape">
<xsl:with-param name="tape" select="$tape"/>
</xsl:call-template>
<xsl:call-template name="validate_start_position">
<xsl:with-param name="start_position" select="$start_position"/>
<xsl:with-param name="tape_length"
select="string-length( $tape )" />
</xsl:call-template>
</xsl:if>
</xsl:variable>
<xsl:choose>
<xsl:when test="$tm_errors = '' and $tape_errors = '' ">
<xsl:variable name="start_state"
select="/turing-machine/states/state[@start='yes']" />
<xsl:call-template name="go_to_next_state">
<xsl:with-param name="step_number" select="'1' "/>
<xsl:with-param name="state" select="$start_state"/>
<xsl:with-param name="tape" select="$tape"/>
<xsl:with-param name="tape_position" select="$start_position"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<!-- Display errors. -->
<xsl:value-of select="$tm_errors"/>
<xsl:value-of select="$tape_errors"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="validate_tm">
<!-- Validate the Turing machine that is described in the source document.
This template returns error messages that describe any errors that
are found. If no errors are found in the source document, then
the template returns nothing.
-->
<xsl:if test="count( /turing-machine ) = 0">
<xsl:text>Error in source document. The document element of the source element must be 'turing-machine'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/@*[ name() != 'version' ] ) != 0 ">
<xsl:text>Error in source document. The 'turing-machine' element contains an unexpected attribute. The only valid attribute for the 'turing-machine' element is 'version'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string( /turing-machine/@version ) != '0.1' ">
<xsl:text>Error in source document. The 'turing-machine' element must contain the 'version' attribute, the value of which must be '0.1'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="/turing-machine/text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. The 'turing-machine' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( /turing-machine/*[ name() != 'symbols' and
name() != 'states' and
name() != 'transition-function' ] )
!= 0 " >
<xsl:text>Error in source document. The 'turing-machine' element contains an unexpected child element. Only the 'states', 'symbols' and 'transition-function' elements are allowed to be child elements of the 'turing-machine' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states ) != 1">
<xsl:text>Error in source document. There must be exactly one 'states' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states/@* ) != 0">
<xsl:text>Error in source document. The 'states' element must not contain any attributes.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="/turing-machine/states/text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. The 'states' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( /turing-machine/states/state ) = 0">
<xsl:text>Error in source document. The source document must include at least one 'state' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states/*[name() != 'state'] ) ">
<xsl:text>Error in source document. The 'states' element contains an unexpected child element. Only the 'state' elements are allowed to be child elements of the 'states' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states/state/* ) != 0">
<xsl:text>Error in source document. A 'state' element must not contain any subelements.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states/state[@start = 'yes'] ) != 1">
<xsl:text>Error in source document. The 'turing-machine' element must contain exactly one start state.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/states/state[@halt = 'yes'] ) = 0">
<xsl:text>Error in source document. There must be at least one halt state.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="/turing-machine/states/state">
<xsl:variable name="matching_nodes"
select="key( 'state', . )"/>
<xsl:if test="count( $matching_nodes ) != 1 and
generate-id( . ) = generate-id( $matching_nodes[1] )">
<xsl:text>Error in source document. There is more than one 'state' element that contains the value '</xsl:text>
<xsl:value-of select="."/>
<xsl:text>'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string-length( . ) = 0 ">
<xsl:text>Error in source document. Found a 'state' element that contains a null value.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./@*[ name() != 'start' and name() != 'halt' ] )
!= 0 ">
<xsl:text>Error in source document. A 'state' element contains an unexpected attribute. The valid attributes for the 'state' element are 'start' and 'halt'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./@halt[. != 'yes' and . != 'no'] ) != 0">
<xsl:text>Error in source document. The 'halt' attribute in a 'state' element has an invalid value. The valid values are 'yes' and 'no'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./@start[. != 'yes' and . != 'no'] ) != 0">
<xsl:text>Error in source document. The 'start' attribute in a 'state' element has an invalid value. The valid values are 'yes' and 'no'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="contains( translate( ., '	

 ', ' ' ),
' ') ">
<xsl:text>Error in source document. The value of a 'state' element contains whitespace.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( /turing-machine/symbols ) != 1">
<xsl:text>Error in source document. The 'turing-machine' element must contain exactly one 'symbols' subelement.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/symbols/@*[name() !=
'blank-symbol'] ) != 0">
<xsl:text>Error in source document. The 'symbols' element contains an unexpected attribute. The only valid attribute for the 'symbols' element is 'start-symbol'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string-length( /turing-machine/symbols/@blank-symbol ) >
1">
<xsl:text>Error in source document. The length of the value of the 'blank-symbol' attribute must not be greater than 1.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/symbols/* ) != 0">
<xsl:text>Error in source document. The 'symbols' element must not contain any subelements.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string-length( /turing-machine/symbols ) = 0 ">
<xsl:text>Error in source document. The 'symbols' element must contain at least one symbol.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="contains( /turing-machine/symbols, $blank_symbol )" >
<xsl:text>Error in source document. The value of the 'symbols' element must not contain the blank symbol.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/transition-function ) != 1">
<xsl:text>Error in source document. The 'turing-machine' element must contain exactly one 'transition-function' subelement.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="/turing-machine/transition-function/text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. The 'transition-function' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( /turing-machine/transition-function/@* ) != 0">
<xsl:text>Error in source document. The 'turing-machine' element must not contain any attributes.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/transition-function/*[name() !=
'mapping'] ) !=
0" >
<xsl:text>Error in source document. The 'transition-function' element contains an unexpected child element. Only the 'mapping' elements are allowed to be child elements of the 'transition-function' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/transition-function/mapping/from/* )
!= 0">
<xsl:text>Error in source document. A 'from' element must not contain any subelements.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( /turing-machine/transition-function/mapping/to/* )
!= 0">
<xsl:text>Error in source document. A 'to' element must not contain any subelements.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="/turing-machine/transition-function/mapping">
<xsl:variable name="matching_nodes"
select="key( 'mapping',
concat( ./from/@current-state,
' ',
./from/@current-symbol
)
)" />
<xsl:if test="count( $matching_nodes ) != 1 and
generate-id( . ) = generate-id( $matching_nodes[1] )">
<xsl:text>Error in source document. There is more than one 'mapping' element whose current symbol is '</xsl:text>
<xsl:value-of select="./from/@current-symbol"/>
<xsl:text>' and whose current state is '</xsl:text>
<xsl:value-of select="./from/@current-state"/>
<xsl:text>'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="./text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. A 'mapping' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( ./@* ) != 0 ">
<xsl:text>Error in source document. A 'mapping' element must not contain any attributes.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./*[name() != 'from' and
name() != 'to'] ) != 0" >
<xsl:text>Error in source document. A 'mapping' element contains an unexpected child element. Only the 'to' and 'from' elements are allowed to be child elements of the 'mapping' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./from ) != 1">
<xsl:text>Error in source document. A 'mapping' element must contain exactly one 'from' sublement.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="./from/text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. A 'from' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( ./to ) != 1">
<xsl:text>Error in source document. A 'mapping' element must contain exactly one 'to' sublement.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:for-each select="./to/text()">
<xsl:if test="translate( ., '	

 ', '' ) != '' ">
<xsl:text>Error in source document. A 'to' element contains non-whitespace text.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
<xsl:if test="count( ./from/@*[ name() != 'current-state' and
name() != 'current-symbol' ] ) != 0 ">
<xsl:text>Error in source document. A 'from' element contains an unexpected attribute. The valid attributes for the 'from' element are 'current-state' and 'current-symbol'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./from[ count( @current-state ) != 1 ] ) != 0">
<xsl:text>Error in source document. Found a 'from' element that does not contain a 'current-state' attribute.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./from[ count( @current-symbol ) != 1 ] ) != 0">
<xsl:text>Error in source document. Found a 'from' element that does not contain a 'current-symbol' attribute.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( key( 'state', ./from[1]/@current-state ) ) = 0 ">
<xsl:text>Error in source document. Found a 'current-state' attribute that contains a value ('</xsl:text>
<xsl:value-of select="./from[1]/@current-state"/>
<xsl:text>') that is not a value of a 'state' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string-length( ./from[1]/@current-symbol ) != 1 ">
<xsl:text>Error in source document. The length of the value of a 'current-symbol' attribute ('</xsl:text>
<xsl:value-of select="./from[1]/@current-symbol"/>
<xsl:text>') is not equal to 1.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="not( contains( $symbols, ./from[1]/@current-symbol ) or
./from[1]/@current-symbol = $blank_symbol
)">
<xsl:text>Error in source document. Found a 'current-symbol' attribute that contains a value ('</xsl:text>
<xsl:value-of select="./from[1]/@current-symbol"/>
<xsl:text>') that is not a symbol in the 'symbols' element and that is not the blank symbol.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./to/@*[ name() != 'next-state' and
name() != 'next-symbol' and
name() != 'movement' ] ) != 0 ">
<xsl:text>Error in source document. A 'to' element contains an unexpected attribute. The valid attributes for the 'to' element are 'next-state', 'next-symbol' and 'movement'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./to[ count( @next-state ) != 1 ] ) != 0">
<xsl:text>Error in source document. Found a 'to' element that does not contain a 'next-state' attribute.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./to[ count( @next-symbol ) != 1 ] ) != 0">
<xsl:text>Error in source document. Found a 'to' element that does not contain a 'next-symbol' attribute.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./to[ count( @movement ) != 1 ] ) != 0">
<xsl:text>Error in source document. Found a 'to' element that does not contain a 'movement' attribute.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( key( 'state', ./to[1]/@next-state ) ) = 0 ">
<xsl:text>Error in source document. Found a 'next-state' attribute that contains a value ('</xsl:text>
<xsl:value-of select="./from[1]/@current-state"/>
<xsl:text>') that is not a value of a 'state' element.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="string-length( ./to[1]/@next-symbol ) != 1 ">
<xsl:text>Error in source document. The length of the value of a 'next-symbol' attribute ('</xsl:text>
<xsl:value-of select="./to[1]/@next-symbol"/>
<xsl:text>') is not equal to 1.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="not( contains( $symbols, ./to[1]/@next-symbol ) or
./to[1]/@next-symbol = $blank_symbol
)">
<xsl:text>Error in source document. Found a 'next-symbol' attribute that contains a value ('</xsl:text>
<xsl:value-of select="./from[1]/@current-symbol"/>
<xsl:text>') that is not a symbol in the 'symbols' element and that is not the blank symbol.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:if test="count( ./to/@movement[. != 'left' and
. != 'right' and
. != 'none' ] ) != 0">
<xsl:text>Error in source document. The 'movement' attribute in a 'to' element has an invalid value. The valid values are 'left', 'right' and 'none'.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
</xsl:for-each>
</xsl:template>
<xsl:template name="validate_tape">
<xsl:param name="tape"/>
<!-- Verify that each symbol on the tape is either the
blank symbol or one of the symbols defined in the
Turing machine.
A null tape is an error.
-->
<xsl:choose>
<xsl:when test="$tape = ''">
<xsl:text>Error. The value of the global 'tape' parameter must contain at least one symbol.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="first_symbol" select="substring( $tape, 1, 1 )" />
<xsl:if test="not( contains( $symbols, $first_symbol ) or
$first_symbol = $blank_symbol
)">
<xsl:text>Error. A symbol on the tape ('</xsl:text>
<xsl:value-of select="$first_symbol"/>
<xsl:text>') is not one of the symbols defined in the Turing machine.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:if>
<xsl:variable name="subtape"
select="substring( $tape, 2 )" />
<xsl:if test="$subtape != '' ">
<xsl:call-template name="validate_tape">
<xsl:with-param name="tape" select="$subtape"/>
<xsl:with-param name="start_position" select="'1'"/>
</xsl:call-template>
</xsl:if>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="validate_start_position">
<xsl:param name="start_position"/>
<xsl:param name="tape_length"/>
<!-- Verify that the start_position is either null or
is a number greater than 0 and no greater then
the length of the tape.
-->
<xsl:choose>
<xsl:when test="$start_position = '' " />
<xsl:when test="string( number( $start_position ) ) = 'NaN' ">
<xsl:text>Error. The value of the global 'start-position' parameter is not a number.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:when>
<xsl:when test="$start_position > string-length( $tape ) or
$start_position < 1" >
<xsl:text>Error. The value of the global 'start-position' parameter is less then one or greater than the length of the tape.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:when>
</xsl:choose>
</xsl:template>
<xsl:template name="go_to_next_state">
<xsl:param name="step_number"/> <!-- Increment for each state transition.-->
<xsl:param name="state"/> <!-- Current state of the Turing machine. -->
<xsl:param name="tape"/> <!-- Current tape. -->
<xsl:param name="tape_position"/> <!-- The current tape position expressed
as the offset (in characters) from
the beginning of the tape.
The tape position for the first
symbol on the tape is 1. If the tape
is "abc" and the Turing machine
is currently pointing to "b", then
the tape position would be 2, since
"b" is the 2nd character in the
tape string. -->
<!-- This recursive named template runs the Turing machine that is
described by the source document. Each call to this template
advances the TM to the next step.
This template assumes that the Turing machine and the tape
have been validated.
-->
<xsl:text>
</xsl:text>
<xsl:text>Step number = </xsl:text>
<xsl:value-of select="$step_number"/>
<xsl:text>
</xsl:text>
<xsl:text>Tape = </xsl:text>
<xsl:value-of select="$tape"/>
<xsl:text>
</xsl:text>
<xsl:text>Tape head </xsl:text>
<xsl:call-template name="display_tape_head">
<xsl:with-param name="tape_position" select="$tape_position"/>
</xsl:call-template>
<xsl:text>State = </xsl:text>
<xsl:value-of select="$state"/>
<xsl:text>
</xsl:text>
<xsl:variable name="current_symbol" select="substring( $tape,
$tape_position,
1 )" />
<!-- Get the mapping for the current state and current symbol. -->
<xsl:variable name="mapping"
select="key( 'mapping',
concat( $state, ' ', $current_symbol )
)"/>
<xsl:variable name="next_state" select="$mapping/to/@next-state"/>
<xsl:variable name="next_symbol" select="$mapping/to/@next-symbol"/>
<xsl:variable name="movement" select="$mapping/to/@movement"/>
<xsl:text>Next symbol = </xsl:text>
<xsl:value-of select="$next_symbol"/>
<xsl:text>
</xsl:text>
<xsl:text>Next state = </xsl:text>
<xsl:value-of select="$next_state"/>
<xsl:text>
</xsl:text>
<xsl:text>Movement = </xsl:text>
<xsl:value-of select="$movement"/>
<xsl:text>
</xsl:text>
<xsl:choose>
<xsl:when test="count( $mapping ) = 0">
<xsl:text>Error. The transition function is not defined for the current state and current symbol.</xsl:text>
<xsl:text>
</xsl:text>
<xsl:text>The Turing machine is crashing.</xsl:text>
<xsl:text>
</xsl:text>
</xsl:when>
<xsl:otherwise>
<!-- We can advance to the next state. -->
<!-- Overwrite the current symbol on the tape with the next symbol. -->
<xsl:variable name="tape_with_next_symbol"
select="concat( substring( $tape, 1, $tape_position - 1 ),
$next_symbol,
substring( $tape,
$tape_position + 1 )
)"
/>
<xsl:variable name="new_tape_position">
<xsl:call-template name="get_new_tape_position">
<xsl:with-param name="tape_position"
select="$tape_position"/>
<xsl:with-param name="movement" select="$movement"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="tape_after_movement">
<xsl:choose>
<xsl:when test="$new_tape_position >
string-length( $tape_with_next_symbol )">
<!-- We have to append a blank symbol to the end of the tape.
-->
<xsl:value-of select="concat( $tape_with_next_symbol,
$blank_symbol )"/>
</xsl:when>
<xsl:when test="$tape_position = 1 and $movement = 'left'">
<!-- We have to insert a blank symbol at the beginninng
of the tape.
-->
<xsl:value-of select="concat( $blank_symbol,
$tape_with_next_symbol )"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="$tape_with_next_symbol"/>
</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<xsl:choose>
<xsl:when test="key( 'state', $next_state )/@halt = 'yes' ">
<xsl:text>
</xsl:text>
<xsl:text>The Turing machine has halted.</xsl:text>
<xsl:text>
</xsl:text>
<xsl:text>Final state = </xsl:text>
<xsl:value-of select="$next_state"/>
<xsl:text>
</xsl:text>
<xsl:text>Final tape = </xsl:text>
<xsl:value-of select="$tape_after_movement"/>
<xsl:text>
</xsl:text>
<xsl:text>Tape head </xsl:text>
<xsl:call-template name="display_tape_head">
<xsl:with-param name="tape_position"
select="$new_tape_position"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<!-- Call ourself recursively, in order to advance to the
next state.
-->
<xsl:call-template name="go_to_next_state">
<xsl:with-param name="step_number" select="$step_number + 1"/>
<xsl:with-param name="state" select="$next_state"/>
<xsl:with-param name="tape" select="$tape_after_movement"/>
<xsl:with-param name="tape_position"
select="$new_tape_position"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template> <!-- go_to_next_state -->
<xsl:template name="display_tape_head">
<xsl:param name="tape_position"/>
<!-- Display the tape head as a pointer (i.e., "^") under the
current symbol. For example, if the tape is "abc" and
'b' is the current symbol, then the tape head would be
displayed as a "^" under the "b".
-->
<xsl:choose>
<xsl:when test="$tape_position = 1" >
<xsl:text>^</xsl:text>
<xsl:text>
</xsl:text>
</xsl:when>
<xsl:otherwise>
<xsl:text> </xsl:text>
<xsl:call-template name="display_tape_head">
<xsl:with-param name="tape_position" select="$tape_position - 1"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="get_new_tape_position">
<xsl:param name="tape_position"/>
<xsl:param name="movement"/>
<!-- Returns the new tape head position after moving the
tape head in the direction specified by the movement
parameter.
-->
<xsl:choose>
<xsl:when test="$movement = 'left'">
<xsl:choose>
<xsl:when test="$tape_position = 1">
<!-- We don't return 0, since a new blank symbol will
be inserted at the beginning of the tape.
-->
<xsl:value-of select="$tape_position"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="$tape_position - 1"/>
</xsl:otherwise>
</xsl:choose>
</xsl:when>
<xsl:when test="$movement = 'right'">
<xsl:value-of select="$tape_position + 1"/>
</xsl:when>
<xsl:when test="$movement = 'none'">
<xsl:value-of select="$tape_position"/>
</xsl:when>
<xsl:otherwise>
<xsl:message terminate="yes">
<xsl:text>Internal error. Bad value for movement.</xsl:text>
</xsl:message>
</xsl:otherwise>
</xsl:choose>
</xsl:template> <!-- get_new_tape_position -->
<xsl:template match="text()"/> <!-- Do nothing. -->
</xsl:stylesheet>"""
expected_1 = """\r
Step number = 1\r
Tape = 199\r
Tape head ^\r
State = go_right\r
Next symbol = 1\r
Next state = go_right\r
Movement = right\r
\r
Step number = 2\r
Tape = 199\r
Tape head ^\r
State = go_right\r
Next symbol = 9\r
Next state = go_right\r
Movement = right\r
\r
Step number = 3\r
Tape = 199\r
Tape head ^\r
State = go_right\r
Next symbol = 9\r
Next state = go_right\r
Movement = right\r
\r
Step number = 4\r
Tape = 199 \r
Tape head ^\r
State = go_right\r
Next symbol = \r
Next state = increment\r
Movement = left\r
\r
Step number = 5\r
Tape = 199 \r
Tape head ^\r
State = increment\r
Next symbol = 0\r
Next state = increment\r
Movement = left\r
\r
Step number = 6\r
Tape = 190 \r
Tape head ^\r
State = increment\r
Next symbol = 0\r
Next state = increment\r
Movement = left\r
\r
Step number = 7\r
Tape = 100 \r
Tape head ^\r
State = increment\r
Next symbol = 2\r
Next state = stop\r
Movement = left\r
\r
The Turing machine has halted.\r
Final state = stop\r
Final tape = 200 \r
Tape head ^\r
"""
def Test(tester):
source = test_harness.FileInfo(string=source_1)
sheet = test_harness.FileInfo(string=sty_1)
test_harness.XsltTest(tester, source, [sheet], expected_1,
topLevelParams={'tape': 199},
title="Universal Turing Machine")
return
|