Wiki Cyclic Tag

From Esolang

Wiki Cyclic Tag is a programming language created by User:ais523 in 2006. It is designed to prove that the MediaWiki software used to run Wikis would be Turing-complete by simulation if it allowed infinite loops. It is based on Bitwise Cyclic Tag.

Contents 1 Syntax 2 Semantics 3 MediaWiki Interpreter 4 Example 5 Computational class

[edit] Syntax

Wiki Cyclic Tag is a matrioshka language; a program consists of a rule and initial data.

• A program starts with the code {{name|, where the name of the interpreter is given instead of 'name'. For instance, a program designed to be interpreted by an interpreter called x1 would start {{x1|.
• The next part of the program is the rule for changing the data. This consists of a list of commands separated with the = character; there is no = at the end. Three commands are available:
  • d Discard the first bit of data.
  • a Append an o bit to the end of the data if the first bit of data is an i bit.
  • b Append an i bit to the end of the data if the first bit of data is an i bit.
• The program is followed by a | character, to separate it from the data.
• The data follows; it consists of o and i bits delimited by = signs. As before, no = sign should be included at the end of the data. o and i are used instead of 0 and 1 because numbers would have a special meaning to MediaWiki in this context.
• At the very end of the program }} must be used.
• Comments can be added anywhere by using the <!-- (this is a comment) --> syntax, the same as in HTML. Comments do not nest; a comment-end trigraph will end all previous unclosed comments.

[edit] Semantics

The d, a, and b commands have been described above. The commands repeat in the order they are given forever. There is one special restriction: there must be at least 2 commands (a 1-command program may be simulated by giving the command twice), and the program must maintain at least 2 bits of data in the data queue at all times, or undefined behaviour will result.

[edit] MediaWiki Interpreter

Line breaks have been here added for clarity. They are not in the interpreter's code. This interpreter only works if named Template:x1.

<nowiki>{{x1&#124;</nowiki>{{{d|}}}{{{a|{{{b|=d&#124;{{{o|}}}{{{i|}}}
&lt;!--}}}=b&#124;&lt;!--}}}=a&#124;&lt;!--{{{d|{{{i|
--&gt;o=&lt;!--}}}--&gt;}}}{{{o|i={{{i|}}}{{{d|&lt;!--{{{a|
--&gt;=i&lt;!--}}}{{{b|--&gt;=o&lt;!--}}}}}}}}}&lt;!--
--&gt;<nowiki>}}</nowiki>

This is an example interpreter for MediaWiki version 1.7. (Some previous versions reject this code.) As MediaWiki does not allow infinite loops, this interpreter outputs the next program step given a program step as input. (Information is input by simply placing the code on a wiki article; the output is displayed onscreen.)

[edit] Example

This corresponds to the Bitwise Cyclic Tag program 01011 with the initial data 1011. The first line is the original program; each line shows the step after the previous line.

{{x1|d=a=b|i=o=i=i}}
{{x1|a=b=d|o=i=i<!--=b|<!--=a|<!--a=bi=o=i=ia=b<!---->}}
{{x1|b=d=a|<!---->o=<!---->i=i<!---->}}
{{x1|d=a=b|<!--=a|<!---->o=<!---->i=i<!---->}}
{{x1|a=b=d|i=i<!--=b|<!--=a|<!--a=bi=i<!---->}}
{{x1|b=d=a|<!--i-->i=i<!--b=d-->=o<!--<!---->}}
{{x1|d=a=b|<!--=a|<!--i=o-->i=i=o<!---->=i<!--d=a<!---->}}
{{x1|a=b=d|i=o=i<!--=b|<!--=a|<!--a=bi=i=o=ia=b<!---->}}

The above with comments removed for clarity:

{{x1|d=a=b|i=o=i=i}}
{{x1|a=b=d|o=i=i}}
{{x1|b=d=a|o=i=i}}
{{x1|d=a=b|o=i=i}}
{{x1|a=b=d|i=i}}
{{x1|b=d=a|i=i=o}}
{{x1|d=a=b|i=i=o=i}}
{{x1|a=b=d|i=o=i}}

[edit] Computational class

Wiki Cyclic Tag is known to be Turing-complete because it can simulate Bitwise Cyclic Tag.