GotoStart Turing-completness proof

← Back to GotoStart

GotoStart can be proven Turing-complete by translating Minsky machine to a language called BranchBlocks, and then translating BranchBlocks to GotoStart.

Minsky machine syntax

Rx is register x (1-indexed). Lx is line x (0-indexed)

Lx inc Rx Ly

Line Lx: Increment Rx and jump to Ly

Lx dec Rx Ly Lz

Line Lx: If Rx is 0 jump to Ly. Else decrement Rx and jump to Lz

BranchBlocks

BranchBlocks code is made out of this blocks (which are called branch-blocks):

branch x (
...
)

which defines branch-block x (0-indexed) with code .... When branch-block is finished running and you dosen't switch to another branch-block then program will halt. First branch-block that will run is 0. Program that dosen't have branch block 0 is invalid.

Branchblocks instructions

Registers are 1-indexed.

inc x

Increment register x.

dec x

Decrement register x.

skip x

Skip next instruction if register x is bigger than 0

switch x

Switch to branch-block x.

Compiling Minsky machine to Branchblocks

Lx inc Rx Ly

would be:

branch Lx (
inc Rx
switch Ly
)

Lx dec Rx Ly Lz

would be:

branch Lx (
skip Rx
switch Ly
dec Rx
switch Lz
)

Lx dec Rx Ly Ly

would be:

branch Lx (
dec Rx
switch Ly
)

Branchblocks to GotoStart

branch x (
...
)

would be:

?(0=x>...)

inc x

would be:

+(x)

dec x

would be:

-(x)

skip x
instruction

would be:

?(x=0>instruction)

switch x

would be:

=(0:x)^

to Infinite GotoStart

In this version

switch x
instructions

is converted to:

=(0:x)?(0=block>instructions)

Where block is the current branch-block If switch is last command in the block the ? command is ommited. Program ends with ^

Examples

Same program that was on Autopsy page

0 inc 1 3
1 inc 1 4
2 inc 2 2
3 inc 1 1
4 dec 1 5 6
5 inc 2 4
6 dec 1 6 6

would become:

branch 0 (
inc 1
switch 3
)
branch 1 (
inc 1
switch 4
)
branch 2 (
inc 2
switch 2
)
branch 3 (
inc 1
switch 1
)
branch 4 (
skip 1
switch 5
dec 1
switch 6
)
branch 5 (
inc 2
switch 4
)
branch 6 (
dec 1
switch 6
)

And then would become:

?(0=0>+(1)=(0:3)^)
?(0=1>+(1)=(0:4)^)
?(0=2>+(2)=(0:2)^)
?(0=3>+(1)=(0:1)^)
?(0=4>?(1=0>=(0:1)^)-(1)=(0:6)^)
?(0=5>+(3)=(0:4)^)
?(0=6>-(1)=(0:6)^)

In Infinite GotoStart:

?(0=0>+(1)=(0:3))
?(0=1>+(1)=(0:4))
?(0=2>+(2)=(0:2))
?(0=3>+(1)=(0:1))
?(0=4>?(1=0>=(0:1))?(0=4>-(1)=(0:6)))
?(0=5>+(3)=(0:4))
?(0=6>-(1)=(0:6))^