From Esolang
Jump to navigation Jump to search

TC proof sketch

Summarized from a discussion on #esoteric at 2014-08-14.

Have a tape layout of [d][s][0][d][s][0]..., where the [d] cells make a data tape, [s] cell next to current [d] holds a "current state" label (reset by each block) and the [0] cells are always zero. Structure the entire program as

 >  #<>#@ AAAA %)<-  #<>#@ BBBB %)<-  #<>#@ CCCC %)<-  #<>#@ DDDD %)

This way, on each loop through the entire program, one of the blocks AAAA, BBBB, ... is executed based on the current state. Each block will set the next state before ending. A block can set the next state value conditionally (based on current [d] being nonzero or not) to, say, 3 or 4 by ending the block with, e.g.,

 ; set [s] to 3, terminate block if [d] zero; set [s] to 4 and terminate block unconditionally

The program will halt if the state is set to N, where N is the number of blocks.

That sounds flexible enough to quite easily translate Brainfuck; make each non-loop sequence of commands a block, and replace [ and ] by blocks that conditionally set the state to whatever the correct block number is.

fizzie (talk) 22:36, 14 August 2014 (UTC)
(all credit: int-e on #esoteric)