Talk:Cratefuck

Proof of bounded storage machine completeness

Consider a warehouse configuration of:

[room 0][storage rooms]

If we enforce that every storage room has a value of 0 or 1, we can have 256 possible storage rooms by using room 0 as the source of bits.

We can reach any of these rooms by simply repeating >. We must eventually return to room 0, which is possible by repeating <. We shall refer to this repetition with reach(n) corresponding to n many >, return(n) is the same but for <.

We can construct clear(room), which clears the room numbered room with this pattern:

reach(room)*[return(room)*]return(room)

This pattern attempts to take the crate in the room, if successful it returns it to room 0. If it is not, it it simply returns to room 0. It actually returns twice if the room is set, but this is acceptable as < at room 0 is a no-op.

Setting a bit is possible with the following construction, set(room):

clear(room)*reach(room)*return(room)

Assuming that the number of storage rooms is limited to 256 then this will always be able to set the room specified to 1.

Something can be done if the value of a room is one, if(room):

reach(room)*[*return(room){code}]return(room)

A similar construction can be used to loop while the value of a room is one, while(room):

reach(room)*[*return(room){code}reach(room)*]return(room)

By using a data room that is guaranteed to be zero as a temporary room, we can flip a room:

if (room)
    clear(room)
    set(flipstore)
# either way, it's cleared now
# so let's set
set(room)
# we set when it needs to be cleared
# correct this
if (flipstore)
    clear(room)
    clear(flipstore)

This always ensures that the temporary room is always zero at the end, and we can therefore have it shared for all flip operations. We can thus notate this as flip(room) with all flips having a shared, implied temporary room.

Copying a room a's value to another b is also possible, copy(a, b):

clear(b)
if (a)
   set(b)

Using these operations, two variants on the conditional are possible, inverted if, ifn(room):

copy(room, flipstore)
flip(flipstore)
if (flipstore)
    clear(flipstore)
    {code}

As well as if-else, if (room) code else code:

copy(room, flipstore)
flip(flipstore)
if (room)
    {if code}
if (flipstore)
    clear(flipstore)
    {else code}

Both of these constructions ensure that the implied temporary room remains zero after operation.

If we have several rooms set aside as a combined integer value represented in binary, we can conditionally execute a piece of code for each possible state of the integer by using a binary tree of if-else statements:

if (msb)
    if (msb+1)
        ...
    else
        ...
else
    if (msb+1)
        ...
    else
        ...

These constructions allow us to construct machines which other Turing complete languages can be translated into.

Constructing TOGA

By setting a room to 1 and never altering it we can have an always-1 room. This can be used to loop indefinitely.

The TOGA(a, b) operation is equivalent to:

flip(a)
if (a)
    jump(b[])
else
    inc(pc[])

We can convert arbitrary TOGA programs into Cratefuck by inserting these constructs into an if-else tree. Jump would therefore set the bits in the indexing integer to an appropriate value. Incrementation is possible using a ripple carry function:

flip(lsb)
ifn (lsb)
    flip(lsb - 1)
    ifn (lsb - 1)
        flip(lsb - 2)
        ...

Finally, wrapping this entire construct in a while loop with the conditional room being the always-1 room allows us to implement a TOGA machine in Cratefuck.

The amount of memory afforded to the machine is given as

N - 2 - pcbits

Where N is 256, and pcbits is the amount of rooms used to represent the program counter. Two rooms are unavailable, as one is used for the always-1 room and the other is used for flips and inverted conditionals.

The amount of Cratefuck instructions required to implement a TOGA program of size n is O(n). This is easily verified by observing that each TOGA instruction corresponds to a fixed number of instructions, the size of each determined entirely by the template and the index of a. Additionally, the code that the instructions are embedded into adds n many + n/2 many + n/4 many, etc. instructions for each level of the if-else tree.

Constructing Smallfuck

The if-else tree can also be used to index a specific room. Simply have each body have a number of > corresponding to the integral value of the indexing binary number. Use < instead to return.

If we redefine our reach and return to use a section of rooms as a pointer to index into this tree, then Smallfuck can be translated into Cratefuck like so:

Smallfuck	Cratefuck
*	flip()
>	inc(ptr[])
<	dec(ptr[])
[code]	while() code

dec(ptr[]) can be implemented as such:

ifn (msb)
    ifn (msb + 1)
        ifn ...
            inc(ptr[])
flip(lsb)
if (lsb)
    flip(lsb - 1)
    if (lsb - 1)
        flip(lsb - 2)
        ...

These constructions can be decomposed to result in a correspondance such that each Smallfuck instruction corresponds exactly to a specific series of Cratefuck instructions.

The amount of cells afforded to smallfuck is given as:

min(2^ptrbits, N - 1 - ptrbits)

Where ptrbits is the number of rooms dedicated to the cell pointer, and N is 256.

The amount of instructions required to implement a Smallfuck program of size n is roughly 2^ptrbits * n, or asymptotically bounded by O(n).

Turing complete extension

Cratefuck can be made Turing complete by increasing the amount of crates in the zeroth room. Cratefuck(n) corresponds to a modified Cratefuck machine such that the zeroth room has n crates. The amount of bits able to be modified is equal to n. If flip and conditionals are used then n - 1 bits are available. Cratefuck(∞) is therefore Turing complete, as it has infinite bits to work with.

stkptr (talk) 02:19, 12 April 2023 (UTC)

Turing completeness proof via Minsky machine simulation

When treated as a Turing machine with a tape and crates used to write symbols, cf quickly runs out of crates.

By using a handful of crates to represent a fixed number (3) of register pointers on an infinite number line we can construct a Minsky machine, which is in the same computational class as a Turing machine.

Outline: Simulate 3 register Portable Minsky Machine Notation, which can use 2 unbounded registers to simulate a standard 2 register Minsky machine, and the 3rd register (can be bounded) is used to simulate arbitrary jumps around the source code. (FWIW I believe 2 reg PMMN is TC, but not trivially so, and deserves a proof. I had a sketch of one, which involved a lot of restructuring to simulate a 2 reg MM with jumps, and suffered from even more slowdown...)

The first room (which starts with the 256 crates) is the NULL room, or home. Every second room represents a number on an infinite number line, and the in-between rooms d represent temporary storage for that location, which helps the seeking algorithm, and should generally be empty. The first d room, adjacent to NULL also stores the result of the dec test (did the last tested register reach zero?).

 NULL, d, 0, d, 1, d, 2, d, 3, ...

Every room can be thought of as potentially containing a 3 bit flag indicating which register pointer is at that point.

• Bit 1 is one crate, for register 1
• Bit 2 is two crates, for register 2
• Bit 3 is four crates, for register 3

Every integer position room can have between 0 and 7 crates. The sum of ALL integer rooms (to infinity) is always 7.

The crane will carry one 'active' crate with it as a temporary marker when seeking and performing actions.

The commands from Portable Minsky Machine Notation we want are: inc(n), dec(n), and while(dec(n)) {} (we don't need if / else). This is roughly equivalent to 3-cell bf (which is TC) and the while loop is what we can implement easily using bf style conditional []s.

Using macros to construct some helpful building blocks:

def init {
  add1
  add2
  add3
}

def next {
   *>[*>*[*<*>*]<*>]
}

def prev {
   *<[*<*[*>*<*]>*<]
}

# Clear test bit:
def clr {
  >*<[*]
}

def seek1 {
  clr
  *
  [* next *<*>*
    [ <*>*  # maybe one
      [ <*>*  # maybe two
        [ <*>*  # maybe 3
          [ <*>*  # maybe 4
            [ <*>*  # maybe 5
              [ <*>*  # maybe 6
                [     # 7
                  * <*>>*<
                ]
                <*[>*<*]>  # 6 = 2 and 3
              ]
              <*[>*<*>>*<<]>  # 5 = 1 and 3
            ]
            <*[>*<*]>  # 4 = 3 
          ]
          <*[>*<*>>*<<]>  # 3 = 2 and 1 
        ]
        <*[>*<*]>  # 2 = 2
      ]
      <*[>*<*>>*<<]>  # 1 = 1
    ]
    >*<*  # Invert found logic
  ]
}


def found {
  <*[>*<*>>*<<]>
}

def notfound {
  <*[>*<*]>
}


def seek2 {
  clr
  *
  [* next *<*>*
    [ <*>*
      [ <*>*
        [ <*>*
          [ <*>*
            [ <*>*
              [ <*>*
                [ * ] # <*>>*< ]  # 7 = 1, 2, 3
                found  # 6 = 2 and 3
              ]
            ]
            notfound  # 4 = 3 
          ]
        ]
        found  # 2 = 2
      ]
      notfound  # 1 = 1
    ]
    >*<*  # Invert found logic
  ]
}

def seek3 {
  clr
  *
  [* next *<*>*
    [ <*>*
      [ <*>*
        [ <*>*
          [ <*>*
            [ <*>*
              [ <*>*
                [ * ]
              ]
            ]
            found  # 7 to 4 = 3 
          ]
        ]
      ]
      notfound  # 3 to 1 = no 3 
    ]
    >*<*  # Invert found logic
  ]
}

def home {
 *[*
    prev
    <*>
    [  # we're at NULL
      *<
    ]

  >*<*
  ]
}


def add1 {
  *>>*<<
}

def sub1 {
  *<<*>>
  *<<*
}

def add2 {
  *>>*<<
  *>>*<<
}

def sub2 {
  *<<*>>
  *<<*>>
  *<<*
}

def add3 {
  *>>*<<
  *>>*<<
  *>>*<<
  *>>*<<
}

def sub3 {
  *<<*>>
  *<<*>>
  *<<*>>
  *<<*>>
  *<<*
}

def inc1 {
  seek1
  add1
  home
}


def inc2 {
  seek2
  add2
  home
}


def inc3 {
  seek3
  add3
  home
}

def dec1 {
  seek1
  sub1
    <*>
    [  # we're at NULL
      >*<<*>>*<
    ]
    >*<*
    [* home ] <
}


def dec2 {
  seek2
  sub2
    <*>
    [  # we're at NULL
      >* <<*>>* <<*>>* <
    ]
    >*<*
    [* home ] <
}

def dec3 {
  seek3
  sub3
    <*>
    [  # we're at NULL
      >* <<*>>* <<*>>* <<*>>* <<*>>* <
    ]
    >*<*
    [* home ] <
}

def while1 {
  *[*
    dec1 >*<*[*
}

def while2 {
  *[*
    dec2 >*<*[*
}

def while3 {
  *[*
    dec3 >*<*[*
}

def endwhile {
    >]*<*<
  ]
}

We now have a basic implementation of a 3 register PMMN system.

We can set r1 to 7 and multiply it by 5, storing the result in r2 using:

init

inc1 inc1 inc1 inc1 inc1 inc1 inc1

while1
  inc2 inc2 inc2 inc2 inc2
endwhile

Which gives a final warehouse state of:

   FINAL: [249, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]

The Null room still has 249 crates. The room representing 0 has 5 crates; 1 + 4 = 0b101 , i.e. registers one and three. 0b010 (Register 2) is in the 73nd room. We subtract 3 to calibrate to zero, and divide by 2 to get the integer represented by that point = 35, which is the result of the code's 7 x 5

While loops can be nested, and more complex examples can be created.

These macros give something equivalent to 3 reg PMMN / 3-cell bf / 2 reg Minsky machine with arbitrary jumps, and therefore proves cf is Turing complete as specified without any more crates. Only about 10 crates are required for this construction. I have tested this construction with the official interpreter (with some debug modifications) and a custom macro compiler. Please let me know if anything looks incorrect. It is difficult to create convincing 2 reg MM examples, but I believe this is complete. Salpynx (talk) 04:48, 2 May 2023 (UTC)