Overload/Turing-completeness proof

← Back to Overload

This is a proof that Overload is Turing complete by User:Fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff. This works by showing that a Turing complete language can be compiled to Overload.

The Turing-complete language

It operates on an array of 1-bit long cells.

Commands:

~x: Flip the bit at cell x
{x ... }x: While x==1 do ...
(x ... )x: If x==1 do ...

It is turing complete because it is basically Boolf**k

Translation

~x    ->  1['x['0]'![]]!['x['1]]x!
{x}x  ->  name[code'1[name]x]  (Loops must be given names)
(x)x  ->  x[code]1

After each command include '1[]'0[]'![].