Turing Completeness Proof of Leafuck

This page presents a proof by User:Rainwave that Leafuck is Turing complete. The proof works by showing that it is possible to compile any Bitwise cyclic tag (BCT) programs to Leafuck. Therefore, since Bitwise cyclic tag is Turing complete, so is Leafuck. It is recommended to read about Bitwise cyclic tag as a prerequisite for this proof so that the explanations here make more sense.

This proof utilizes an intermediate language named MarkerHelper. The first part of the proof shows how to compile BCT to MarkerHelper, then the second part shows how to compile MarkerHelper to Leafuck.

MarkerHelper

MarkerHelper operates on two dynamically growing linked list, $P$ and $D$. Initially, both $P$ and $D$ have exactly 1 node, called the head of each respective list. The last node of each list is called its tail.

Each node in the lists can have a set of markers. A marker is a field of the node that can either be present or absent. When a new node is created, its set of markers is empty.

A pointer points to one node, initially the head of $P$.

MarkerHelper provides the following primitives:

Primitive	Description
m!	Add marker m to the current node. If the marker already exist, ignore this command.
%	If the pointer is at $P$'s head, set it to $D$'s head. If the pointer is at $D$'s head, set it to $P$'s head. Otherwise, this instruction is undefined.
>	Set the pointer to the next node in the current list. If the current node is a tail, this instruction will create a new node before setting the pointer to the new tail.
<	Set the pointer to the previous node in the current list. If the current node is a head, this instruction is undefined.
m(x)	While current node has marker m present, execute x.
f = g	Define a subroutine f with instructions g.
{f}	Call subroutine f.

Compiling BCT to MarkerHelper

Building the production rules

Assuming the pointer is currently at the head of $P$, BCT production rules can be mapped as follows

BCT Command	MarkerHelper mapping
10	>np0!n1!nhead!ntail!
11	>np0!n0!nhead!ntail!
0	>np1!nhead!ntail!

Important: The ntail marker should be omitted when mapping the last production rule.

Note that all markers are prefixed with "n-" which means 'not'. So, n0 means not zero, nhead means not head, etc. This negative naming convention is intentional.

After all production rules are processed we can move back to the head of $P$

goToHead = nhead(<)

As an example, the following BCT production rules:

10011

can be mapped to MarkerHelper as follows:

initializeP = nexist!ntail! >np0!n1!nhead!ntail! >np1!nhead!ntail! >np0!n0!nhead! {goToHead}

Simulating the cyclic behavior of the production rules

The execution of the production rules in BCT can be modeled with a queue where after executing the command at the head of the queue, it is immediately moved to the tail of the queue. This has the same effect as the commands being executed in cycle. To achieve this, instead of deleting the first element whenever we pop the queue, we instead activate its nexist marker. When new element is added, we activate the ntail marker of the previous last element.

Here are some subroutines that we can use when dealing with this queue

goToFirstElement = nexist(>)
goToTail = ntail(>)
moveFrontToBack = {goToFirstElement}nexist!
    np1({goToTail}ntail!>np1!nhead!{goToHead})
    np0(
        n0({goToTail}ntail!>np0!n0!nhead!{goToHead})
        n1({goToTail}ntail!>np0!n1!nhead!{goToHead})
    )

Simulating the data string

It is known that BCT is Turing complete even if the data string starts with just a single 1. Therefore, assuming the pointer is currently at the head of $P$, we can initialize $D$ as follows

initializeD = %nexist!ntail! >nhead!n0! <%

Assuming the pointer is normalized at the head of $P$ before each step, simulating a single step of the a BCT program can be done as follows

step = {goToFirstElement}
    np1({goToHead}%{goToFirstElement}nexist!{goToHead}%)
    np0({goToHead}%{goToFirstElement}
        n0({goToHead}%{goToFirstElement}
            n0({goToHead}%{goToTail}ntail!>n0!nhead!{goToHead}%)
            n1({goToHead}%{goToTail}ntail!>n1!nhead!{goToHead}%)
        )
        n1({goToHead}%)
    {moveFrontToBack})

To make it execute indefinitely we just have to add an nhalt marker at the head of $P$ and wrap the whole execution in an infinite loop.

BCT = {initializeP}{initializeD}nhalt!nhalt(step)

Compiling MarkerHelper to Leafuck

Let the left child of the root node be the head of $P$ and the right child of the root node be the head of $D$.

We can embed the linked lists the following way:

• The right child of a node is the next node in the linked list.
• The left subtree of a node is reserved for its markers.

Representing markers

Markers can be laid down in parallel

    Previous node
          \
      A node in P
          / \
         O   Next node
        / \
       O  np0
      / \   \
     O  np1  O
    / \
   O   n0
  / \   \
...  n1  O

Here, active markers have a dummy right child, making them not leaves. This structure makes activating and accessing a marker as simple as executing a hardcoded string of instructions.

Instructions mapping

Each MarkerHelper primitive can then be mapped like this

Primitive	Mapping
%	^> or ^< depending on whether we're coming from $P$ or $D$, which we know at compile time.
>	Just >.
<	Just ^.
m!	$n$ copies of <, followed by >>^^, followed by $n$ copies of ^. For example: <<< >>^^ ^^^. The number $n$ dictates which marker to activate.
m(x)	<<< >[^ ^^^ x's logic <<< >]^ ^^^ The general pattern for <<< >[^ ^^^ is $n$ copies of <, followed by >[^, followed by $n$ copies of ^. The number of $n$ dictates which marker to check for the conditional.

The f = g and {f} primitives are just compile time constructs that do not affect the runtime behavior of the programs.