Talk:3L

TC proof

I am currently trying to implement reversible counter machine into it. I made this command list for an intermediate language:

right - flip a register's flip and move right
left0 - move left, only works when register's flip is 0
left1 - move left, only works when register's flip is 1
shiftr0 - increment current cell and decrement next cell, unless it is the last cell, only works if register's flip is 0
shiftl0 - decrement current cell and increment next cell unless this is the last cell, only works if register's flip is 0
shiftr1 - increment current cell and decrement next cell, unless it is the last cell, only works if register's flip is 1
shiftl1 - decrement current cell and increment next cell unless this is the last cell, only works if register's flip is 1
abc/xyz - if zero jump to abc, else to xyz (same restrictions apply to jumps as in counter machines)

Besides a value (unsinged integer of unbouned value) each register also has a boolean value called a flip, it doesn't make much sense outside the context of 3L but reason it exists is mainly when searching through the tape it would flip values when moving right.

Now it needs to be translated into 3L, which I don't think will cause much problems. Basic idea is to represent counters like that:

0 1 0 0 0 ... 0 0 0 1 0 1 0 0 0 ... 0 0 0 1 0 ...

It could be sometimes flipped, as I explained before. Counter with a value $n$ would be represented as unary string of $3n$ 0s or 1s depending on the flip value. Searching while moving left is easy (in fact infinite loop example basically does that, just that there is no end value for it) the but while moving right is more difficult, so I will add them later. I am not sure if I'm going in the right direction. --ChuckEsoteric08 (talk) 15:35, 27 September 2026 (UTC)