# 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)