GotoStart Turing-completness proof
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))^