Talk:Minsky Swap

Computational Class

I'm fairly certain this can be showed to be simulatable by a 1-counter Minsky machine. If anyone knows of a resource proving that a 1-counter Minsky machine is non-TC, it would save me from writing that part of the proof.

If you allowed jumps to be fully general, so that increments and successful decrements don't have to continue to the next command, I believe this language could be showed Turing-complete by simulating a Minsky machine with an arbitrary number of counters, using the prime factorization of one of the registers. Caenbe (talk) 22:03, 23 July 2020 (UTC)

I don't know of a resource offhand but I can say with certainty that the normal 1-counter MM is not TC. To do any kind of a more complex calculation, such as testing if a value can be divided by 2, you need to be able to copy the original value in one form or other into another counter. For example, try multiplying a counter's value by 3 in 1-counter MM and you'll see the root of the problem. --Keymaker (talk) 07:49, 24 July 2020 (UTC)

On further reflection, this language can simulate a 1-counter MM. Just use one register for counting and switch to the other one when you need to make an arbitrary jump. Since the halting problem for this lang and a 1-counter MM are equivalent (and that's all we have to go on without I/O), I propose this language should be in the Push-down automata catgeory. Caenbe (talk) 16:41, 5 June 2021 (UTC)

Computational Class Correction

The current Computational class section Special:PermanentLink/84131#Computational_class is incorrect. This langauge should be Turing complete as it can directly simulate a 2 register Minsky machine.

Relationship to 1-reg MM

• Minsky Swap is more powerful than a 1 register Minsky machine, and cannot be simulated by one.

• Minsky Swap can trivially simulate a 1 register Minsky machine by only making use of the + and ~ commands. This is a 1 register Minsky machine by definition.

In a 1-reg Minsky machine a jump only occurs if the register is zero (as described by Minsky, and in this article), so the only way to have endless jumps is for the register to repeatedly reach zero. Simplest form:

   decnz(1);

(using 1 indexed line numbers per Readable Minsky Swap Notation described in the article).

Minksy Swap can endlessly increase one register as follows:

swap();
inc();
inc();
inc();
inc();
inc();
swap();
decnz(1);

There is no way to simulate this in a 1-reg Minsky machine, so a 1-reg MM cannot simulate Minsky Swap.

2-reg MM simulation; TC proof

Minsky's 2-register machine (sec 14.1 of Computation: Finite and Infinite Machines ) uses 2 registers, r, and s and has 4 commands in its most basic form:

• r⁺ : inc(); for register 1: r
• r^-(n) : decnz(N); for r (jump happens iff register IS zero)
• s⁺ : inc(); for register 2: s
• s^-(n) : decnz(N); for s (jump happens iff register IS zero)

Any Minsky 2-register machine code can be translated unambiguously to Minsky Swap as follows:

2-reg MM	MS
r+	+
r-(N)	~(N)
s+	*+*
s-(N)	*~(N)

Furthermore, for every target N of any jump, insert a double-swap / no-op: **. For any 2-reg MM source code, there will be a finite number of these. As a no-op, they do not affect the program behaviour. Then adjust the N of every jump instruction to point to the first * (swap) if it is a r^- or to the second * (swap) if it is a s^-.

This way the intended r or s register is always correctly targeted for any possible path through the code, and the various decnz(N) have a fixed register every time they are encountered.

This adding of no-ops to jump targets is probably unnecessary for Turing completeness. If anything, allowing the same block of code to target either register 1 or 2 depending on how it was jumped to gives the language more flexibility and reduces the amount of code needed to get a potential effect, but it makes it harder to reason about. Adding the no-ops and fixing the target registers so that register 1 is always current upon entering and exiting a composite-command makes the 2-reg Minsky machine translation clear.

Salpynx (talk) 23:55, 1 June 2022 (UTC)

I don't think the 2 counter Minsky Machine you're describing is TC. If jumps are only possible when a counter reaches zero, something similar to my earlier proof applies. Try dividing a counter by 2 and you'll see you need to be able to jump backwards when a decrement DOESN'T result in zero. Caenbe (talk)

Yeah, you are completely correct, as specified this language in not TC. Well done for picking it up, and thanks for calling it out! I quickly checked some of my old notes because I thought I'd figured out 2-reg Minsky machines tricks. Turns out I wrote this a couple of months before I figured out all the variations and that an arbitrary jump, go(z), or a jump if the test result is non-zero, as I think you are suggesting above, is needed for a TC 2 register machine. Having more than 2 registers doesn't strictly require this. My notes are in my user space here: https://esolangs.org/wiki/User:Salpynx/Minimal_TC_program_machines which I wrote in September 2022, three months after writing this proof. On that page I write "Generalised Minsky Swap (TC, but not as currently specified on wiki)" ... so apparently I'd figured out the proof was flawed and didn't update anything. Sorry.

It looks like I'd decided the language should be "corrected" by modifying the + command to be "Increment the register under the register pointer and jump to command M, where M is the Nth number in the jump line and this ~ is the Nth tilde in the code line", which matches Minsky's 1967 Theorem 141-1, "Generalised Minsky counter machine" with two registers and two commands, which both take a jump argument for the next instruction, and _is_ TC. I think this is justified because this language was intended to be a proper 2 register Minsky machine with a swap command. That's what I wanted for some reason back then, so I found the modification that worked and ran with it. I'm not sure the etiquette of 'correcting' a flaw in a language spec like this. My "proof" above still needs to be fixed to use inc(N) for it to be valid too. Salpynx (talk) 21:33, 20 January 2024 (UTC)

Also: Buggy Python interpreter

The linked Python Minsky Swap interpreter is buggy: it always increases the jump / tilde count (val) so a jump is to the nth number where n is the number of tildes encountered in the program execution so far, instead of the number of tildes in the source code (which it should be according to the spec). Currently the interpreter can't run any infinite loops, not even a simple 1-reg MM example loop:

 **~
 1 1 1

(more symbols than strictly required because it's not very clear whether the spec or implementation expects symbols to be 0 or 1 indexed -- this covers both) Salpynx (talk) 23:55, 1 June 2022 (UTC)

---

My bad, I believe I've fixed the bug. The interpreter assumes one-based indexing. - Bangyen (talk) 03:10, 2 June 2022 (UTC)