<!-- DTD for the Turing Machine Markup Language (TMML), version 0.1. A TMML document specifies a Turing machine. For more information about Turing machines and TMML, please refer to the XSLT stylesheet that is available at http://www.unidex.com/turing/utm.xsl. This stylesheet is a Universal Turing Machine that executes the Turing machines that are defined by TMML documents. This DTD is available at http://www.unidex.com/turing/tmml.dtd. Developed by Bob Lyons of Unidex, Inc. Please email any comments about this DTD 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 DTD 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 DTD. 2. The DTD is licensed to the user on an "AS IS" basis. Unidex Inc. makes no warranties, either express or implied, with respect to the DTD 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 DTD will be uninterrupted or error-free, or that defects in the DTD will be corrected. You the user are solely responsible for determining the appropriateness of the DTD 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. --> <!-- A Turing machine consists of symbols, states and a transition function. --> <!ELEMENT turing-machine ( symbols, states, transition-function ) > <!-- The turing-machine element must contain the version attribute, which must be equal to "0.1". --> <!ATTLIST turing-machine version CDATA #IMPLIED > <!-- The symbols element defines the symbols supported by the Turing machine. Each character in the content of the symbols element is a member of the set of symbols. Thus, each symbol is a Unicode character. At least one symbol must be defined by the symbols element (in other words, the length of the content of the symbols element must be at least one). The blank-symbol attribute of the symbols element defines the blank symbol for the Turing machine. By default, the blank symbol is the space character. None of the symbols that are defined by the content of the symbols elements may be the blank symbol. Each symbol on the input tape must be equal to the blank symbol or one one the symbols defined in the content of the symbols element. --> <!ELEMENT symbols (#PCDATA) > <!ATTLIST symbols blank-symbol CDATA ' ' > <!-- The states element contains one or more state elements. --> <!ELEMENT states ( state+ ) > <!-- Each state element defines a state in the Turing machine. The value of each state element must not be null and it must not contain any whitespace characters. Also, the states must be unique. In other words, if one of the state elements contains "state1", then none of the other state elements may contain this value. There must be exactly one start state. The initial state of the Turing machine is the start state. The start state is the state element that includes the start attribute that is set to 'yes'. There must be one or more halt states. The Turing machine halts when it enters one of the halt states. A halt state is a state element that includes the halt attribute that is set to 'yes'. --> <!ELEMENT state ( #PCDATA ) > <!ATTLIST state start (yes|no) 'no' halt (yes|no) 'no' > <!-- The transition function maps the current state and the current symbol to the next state, the next symbol and the movement for the tape head. The transition function contains one or more mappings. Each mapping maps from a ( state, symbol ) pair to a ( state, symbol, movement ) triplet. --> <!ELEMENT transition-function ( mapping+ ) > <!-- A mapping consists of the from-side of the mapping and the to-side of the mapping. The from-side of each mapping must be unique. For example, if there is a mapping element in which the the current state is "x" and the current symbol is "1", then must not be another mapping element in which the current state is "x" and the current symbol is "1". --> <!ELEMENT mapping ( from, to ) > <!-- The from element contains the current-state and current-symbol attributes. The current state is the state that the Turing machine is in when it invokes the transition function. The current symbol is the symbol on the tape under the Turing machine's tape head when the Turing machine invokes the transition function. The value of the current-state attribute must be one of the states defined in the states element. The value of the current-symbol attribute must be one of the symbols defined in the symbols element or must be equal to the blank symbol. --> <!ELEMENT from EMPTY > <!ATTLIST from current-state CDATA #IMPLIED current-symbol CDATA #IMPLIED > <!-- The to element contains the next-state, next-symbol and movement attributes. Each time the Turing machine invokes the transition function, it changes its state from the current state to the next state. It then overwrites the current symbol on the tape with the next symbol. The Turing machine then moves its tape head one symbol to the left, one symbol to the right or not at all, depending on the value of the movement attribute. The value of the next-state attribute must be one of the states defined in the states element. The value of the next-symbol attribute must be one of the symbols defined in the symbols element or must be equal to the blank symbol. The value of the movement attribute must be 'left', 'right' or 'none'. --> <!ELEMENT to EMPTY > <!ATTLIST to next-state CDATA #IMPLIED next-symbol CDATA #IMPLIED movement (left|right|none) #IMPLIED >