User:Hillgentleman/gniruT

Modelling the Turing machine

Since recursively substituted templates can perform a lot of tasks , it is natural to ask, can it simulate a universal Turing machine, i.e., can one build a model of a universal Turing machine with templates in principle, neglecting the pre-and post-expansion size limits?

The first obstacle is that the number of variables that a template can take is finite. We may try to go around this by category:replicator templates, such as Template:Tiv or Template:Tiv, which replicates. Suppose we start with a template call,

{{subst:some random call|0|0|0 ......|1|0|1|.....|0|0|0|0|0}}

with 100 parameters, mostly 0, with a few 1's in middle. We may programme a it in such a way that it "freezes" when a 1 reaches its left or right edge and become just a string... it doesn't work.

Can we make the following work?

However, if we allow ourselves editing the "machine" page as well, we may try to let it produce longer and longer "machines" successively, with a three-level ("target, machine and machine producer") system, e.g. (something like) the code

<noinclude>{{subst:produce replicator|n=17}}</noinclude>{{<includeonly></includeonly>subst:replicator|{{{1}}}|{{{2}}}|... {{{17}}}}}<noinclude></noinclude>

where the "machine producer" template:produce replicator would look like, e.g.

{{<includeonly></includeonly>subst:subst}}produce replicator |{{<includeonly></includeonly>subst:#expr:{{{n}}}+1}}}}  
{{<includeonly></includeonly>subst:endnoinclude}}
{{<includeonly></includeonly>subst:includeonlysubst}}replicator|{{<includeonly></includeonly>subst:replicator/generate|n={{{n}}}}}
{{<includeonly></includeonly>subst:noinclude}}

where template:replicator/generate should be a copy something like template:replicate+0/generate or perhaps better template:rule 30 long/generate; and the templates template:noinclude and template:endnoinclude are the noinclude tags <n o include> </n o include>

Then we may altenate our edits between the "target" page and the "machine" page (in this case template talk:replicator and template:replicator respectively); whilst the machine keeps running on the target page, the "machine producer" (in this case template:produce replicator) keeps producing longer and longer machines on the "machine page".