Talk:Incdecisive Machine

A simpler Minsky Machine to Incdecisive Machine translation

This translation uses the same counters for the two machines, but with the values offset by 1 (so that a counter with value 0 in the Minsky Machine has value 1 in its Incdecisive Machine translation):

• Decrement-and-zero-test: split into a separate decrement and zero test
• Decrement, increment (without control flow): these instructions also exist in Incdecisive Machine (pick the next line as the goto target for an increment)
• Zero test: decrement then increment the counter (jumps if non-zero)
• Unconditional jump: pick an arbitrary counter, increment it (jumping to the jump target), then decrement it at the jump target (it's trivial to rewrite a program so that jump targets aren't reached via normal control flow, only by jumps, by adding extra jumps immediately before them, so without loss of generality the extra decrement doesn't affect anything)

You need to start the program by incrementing all counters, but that's easy enough, and then you have essentially the same program running with the same counters. So Incdecisive Machine is Turing-complete on two counters because Minsky machines are. --ais523 23:30, 22 September 2022 (UTC) 23:30, 22 September 2022 (UTC)

Thanks! An elegant proof which would have saved me a lot of trouble with my 2-register translations. A small consolation is that by crafting them especially for this language they should provide more optimal 2-register translations for this language than programs compiled into Minsky Machine's instruction set and then translated into Incdecisive Machine. But it won't be much of a difference... I'll try to keep this technique in mind for future needs. I should at the very least have realized that using an additional always-larger-than-one register could be replaced with additional increments and decrements -- which would have saved me from the 2-register work just as well. Somewhat ironic that I was using two registers for the 2-register proof and accomplishing everything without any additional registers and not thinking twice about it... My mistake was in not realizing the connection of these two ideas. I didn't think the simple translation any more than I needed to, the additional register idea was the first quick idea I got and so I just kept it and didn't think any more of it, my mind was already set on the idea that 2-register translation needed a completely different approach -- which was true enough, but I never thought the obvious, that n-register Minsky Machine could be translated into n-register Incdecisive Machine (and along with it, any 2-register Minsky Machine program), all I saw were a generic n+1 translation and a specific 2-register translation... This is a kind of eye-opener for me right now. --Keymaker (talk) 10:04, 23 September 2022 (UTC)

It's just crossed my mind that a similar approach could be used for the more normal type of Minsky machines where the zero test is part of the decrement, but with mostly sequential control flow – if your control flow operation is "decrement and jump if nonzero", then it's possible to construct an unconditional goto via incrementing and decrementing an arbitrary register, so the lack of arbitrary jump instructions ends up not mattering. --ais523 20:06, 23 September 2022 (UTC) 20:06, 23 September 2022 (UTC)