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)
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
-cancels with the first line of a following
-; similarly for
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
Observation: This also gives a depth-2 construction for finitely many unbounded cells by simply implementing
-, 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: ...
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)