Talk:Stun Step

Suggestion

I'd like to suggest a small modification: that the main loop only repeats if the current tape element is zero (or if you prefer, the opposite, if you let it initialize as zero). That way it becomes more reversible as you can determine whether a given iteration is the first (if the tape element started non-zero), and you get (presumably) Turing completeness in the usual sense with halting and final state. --Ørjan (talk) 18:44, 25 July 2018 (UTC)

Also, this will make it easier to translate to other reversible languages (depth two nesting reversible boolfuck/brainfuck seems like an obvious candidate), otherwise they'd need an iteration counter or something. --Ørjan (talk) 01:08, 26 July 2018 (UTC)

Yes, that's a good idea; I updated the specification. (The modification doesn't change any of my plans for the language.) --ais523 01:44, 26 July 2018 (UTC)

Reversible Brainfuck

My promised translation to Reversible Brainfuck with depth two nesting. Not sure whether to put it in an article until computational class is decided.

• Tape length arbitrary bounded, but shown for 5.
• Uses only values 0 and 1.
• Lines starting with @ can be removed to change wrapping into undefined behavior.
• The last line of + or - cancels with the first line of a following + or -; similarly for > and <.

Initial layout
   @ 011110                    Wrapping guide
   @  11111                    Non-wrapping guide
   @ 000000                    Wrapping intermediate/first flag
      00000                    Movement flags/digit border
      11110                    First unary digits interleaved
      00000                    End of digits

Initialization
   @ >+>+>+>+>> +>+>+>+>+> >>>>>>
     >>>>> +>+>+>+> [

End of program
   ]

+
   <<<<< [>>>>>]               Go to end of digits
   + >>>>>                     Add digit
   [<<<<<] >>>>>               Go back to first digit

- (+ reversed)
   <<<<< [>>>>>]               Go to end of digits
   <<<<< -                     Remove digit
   [<<<<<] >>>>>               Go back to first digit

>
     [<<<<< + >>>>>] <<<<<     Set flag (0 to move) and go to it
   @ [<<<<<] <<<<< < <<<<<     Go to guide
   @ [<]                       Possibly wrap
   @ >>>>> > >>>>> [>>>>>]     Go back to flag area
     [>]                       Possibly move
     >>>>> [<<<<< - >>>>>]     Unset flag and go to first digit

< (> reversed)
     [<<<<< + >>>>>] <<<<<     Set flag (0 to move) and go to it
     [<]                       Possibly move
   @ [<<<<<] <<<<< < <<<<<     Go to guide
   @ [>]                       Possibly wrap
   @ >>>>> > >>>>> [>>>>>]     Go back to flag area
     >>>>> [<<<<< - >>>>>]     Unset flag and go to first digit

--Ørjan (talk) 17:34, 26 July 2018 (UTC)

Observation: This also gives a depth-2 construction for finitely many unbounded cells by simply implementing + and - as + and -, replacing the unary digit sequences with single cells. (A hunch says that won't give a minimal number of cells though...) --Ørjan (talk) 01:44, 28 July 2018 (UTC)

Ideas for TC proof

<ais523> the issue is that we don't have any TCness proofs for reversible counter machines yet, and it's fairly difficult to emulate anything using a reversible counter machine other than other reversible counter machines

I haven't managed to keep myself from thinking a bit generally about this, and had the same thought.

I think that it might be an idea to go in three steps:

• from Reversible Brainfuck with 1 bit cells (which I already proved TC)
• via Reversible Brainfuck with a finite number of unbounded cells, by implementing a tape of bits in some of them.
• to Stun Step, possibly using a similar technique as for my Home Row proofs.

Reversible Brainfuck when re-encoded with IFs and GOTOs can be seen as having just one additional restriction on branching: All conditional statements must be paired with another one.

GOTO L2 IF R; LABEL L1: ...
GOTO L1 IF R; LABEL L2: ...

Hopefully this restriction can be used to make the branching work reversibly. --Ørjan (talk) 01:39, 28 July 2018 (UTC)

As you may have seen, I just completed the Reversible Brainfuck part, so now we do have a TCness proof for a type of reversible counter machine. (In fact you get ordinary "Minsky" ones as a corollary, although that must be already known somewhere.) --Ørjan (talk) 02:18, 15 August 2018 (UTC)

I eventually managed to make it work through Bouncy Counters and Delta Relay. But I don't think I'd have figured out the proof for Bouncy Counters without doing Flow of Holes first (it didn't translate perfectly, but translated well enough that the bit bucket still worked, which is the important part.) --ais523 07:17, 1 October 2024 (UTC)