Turing Machine

1. XSLT as Turing Complete
2. XSLT Turing Machine

1.

XSLT as Turing Complete

Michael Kay

A more direct demonstration of XSLT's Turing-completeness was done a while ago, see unidex.com

2.

XSLT Turing Machine

Alexandr Korlyukov

I have the Turing machine in XSLT.

The stylesheet does use the xt:node-set instruction, thus, you should use James Clark's XT to execute the stylesheet.

I do not use built-in XSLT functions of arithmetics, and also the functions for working with lines of symbols.

Sequence of symbols of a tape I represent as a tree. At each level of the tree there are one symbol and reference to other part of the tape.

The instructions for the Turing machine are similarly represented also.

Example 1. Replacement of each unit by two.

Example 2. Doubling of quantity of units on the tape. If, for example, on the tape in the beginning there are 10 units, then in the end will be 20 units.

Example 3. Check of structure of brackets. At the end of working in the free square there will be T, if structure correct, and F - if wrong.

Example 4. Deleting of points between units. For example, if in the beginning on the tape there were symbols ".11..1.1...", then in the end we shall have "1111".

Example 5. Check of divisibility on 3. Similarly, it is possible to make the program of check of divisibility on 9.

For more details, please see the web site

professor, the Grodno State University

Also shown at unidex.com