Wiki Cyclic Tag

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.

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.

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.

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.)

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}}

Computational class

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