User talk:Salpynx/Minimal TC program machines

Autopsy is TC

Your table is a bit wrong; Autopsy proof relies on { inc(r, z), jzdec(r, z) } (arbitrary jump after increasing register) variation, which definitely is Turing-complete. Not { inc(r), jzdec(r, z) } as you for some reason thought. A number of esolanguages cannot halt but are considered Turing-complete (I/D Machine for example) because the halting can be simulated in a program-specific way, 'tailored' for each program; for instance the program A in language B can end in infinite jump from instruction X to instruction X, from which an outside observer can detect that the program has halted. And yes, an interesting question what { inc(r), jzdec(r, z) } actually is... --Keymaker (talk) 09:08, 15 September 2022 (UTC)

Thanks for commenting! I see where I went wrong now, sorry. There was something in the summary and proof that made me think there might be a issue with the MM. The proof looked a solid demonstration of equivalence, but I thought it might be starting from an overly limited MM. My head was swimming with different notations for the same, or similar, but subtly different machines and I knew I had to come back and check Autopsy later. When I did, I took a terrible shortcut by noticing the code for mmtoautopsy.py took less args to INC than DEC... so I (somewhat correctly) concluded it couldn't be { inc(r, z), jzdec(r, z) } (an equal 2 args each) and then jumped to the incorrect assumption it must be the limited one, where INC has one less arg (no jump). My bad. What I see now is that you used:

• { inc(r, z), dec(r, zTRUE, zFALSE) }

with two z targets from every DEC. I haven't seen dec(r, zTRUE, zFALSE) in Minsky (1967 at least), but I had noticed it on the Wikipeida list. I initially ignored it completely as it wasn't 'minimal' and I was too fixated on minimisation. I see now that it is the best generalisation; why have one out three possible transitions have an implicit concept of some special linear 'next instruction'? With this form, every transition is explicit. Thinking this through gave me an idea for a simple graph notation for these counter machines, which I'll write up soon. The bulk of my recent MM code was branch labels which suggests structure is the more interesting part of these programs. This dec(r, zTRUE, zFALSE) insight makes me want to explore the topology and structure of counter machines now.

I picked Autopsy as a target to test ideas against because it had such a thorough proof to test... and interesting ideas. The different step amounts, automatic register advancement, and implicit looping were all an extra layer to reason through, and I was still trying to get a handle on some of the basics, so I tangled myself. I'm hoping to come back to Autopsy as a possible 'compile target' for whatever I'm working on, if it turns into a counter machine cross-compiler. Thanks for putting me right! I totally agree now that the 2 reg { inc(r, z), dec(r, zTRUE, zFALSE) } MM in your proof is unambiguously TC, and I'll correct my table! Salpynx (talk) 21:36, 15 September 2022 (UTC)

The confusion was certainly understandable. No problem. Funny that you weren't aware of that Minsky variation! To me it has always been the variation. But I'm not familiar with almost any of the old literature and I'm more or less unable to read it, so I've never been able to trace the formation of those machines. When I got into counter machines I just somehow got the impression that this variation was the Minsky Machine everyone used (although nobody almost ever seems to use Minsky Machines). I think this variation is the best precisely because every transition is defined directly. It feels different, somehow more complete. Makes translating a little bit simpler too.

Counter machines are interesting, yes. There are some interesting questions about program structure that, to my knowledge, are unknown. But they are subtle cases and I can't remember them offhand right now; just things that have come across as I've thought about translations (of MM into other languages). I should dive into my notes some day and do something about them...

CMNN seems like an interesting project. Will there be software to generate these graphs? Related to this, one thing I'd like to see, and which I believe would work well with Minsky Machine, is a visual 'design studio' for programs. Place instruction nodes (that contain the register information), draw edges presenting transitions. Too bad it's beyond my skill even though it wouldn't be much of a project for someone who can do graphics programming / interactive programs. This kind of programming environment might make counter machine programming so different, easier -- perhaps even intuitive. (Whether anyone in the world has such use for them that they need the programming at the 'machine level' to be easier is a different question.)

Also, yesterday I got a new idea related to Minsky Machine. I'm working on specs and translation software as I speak. I think it will be quite interesting, for the few people caring about these things. I hope to get the project out in a few days. --Keymaker (talk) 10:11, 16 September 2022 (UTC)

For the sake of anyone reading this in the future, here is the language I was working on: Incdecisive Machine. Quite funny: It appears that my idea is pretty much the same that you just added to the list some hours ago -- Minsky's "Jump-and-decrement-if-not-zero". But I was not aware of this variation... So the variation I thought of some days ago did this, but in a reversed way: It jumps to an arbitrary instruction if the register's value was larger than 0 at the time it was increased, and goes to the next instruction if the value changed from 0 to 1. The decreasing instruction decreases the value if it's larger than 0, but does not branch, just goes to the next instruction. I feel my variation is a bit easier to program in, conceptually, but that is probably just because I've been exposed to it for the past few days. --Keymaker (talk) 12:45, 20 September 2022 (UTC)

That looks like a great addition to the family! :) Funny I had just noticed the significance of the "decrement and jump" ⊖ instruction in Minsky. I had read it before, and took it to be an equivalent alternate version of the "Jump-if-zero". I have been working on a theory which classifies Portable Minsky Machine Notation as a restricted subset of something I'm referring to as "the hypothetical Minsky machine language" (with a number of equivalent 'dialects'). I believe all PMMN programs *are* Minsky machines, but not all Minsky machines are directly expressible in PMMN. I found a relatively simple n+1 construction to convert them (I'm interested to check your n+1 construction, and really like your technique of defining the algorithm in code once a few test examples have been worked out to test it properly). I was pretty sure 2 register PMMN was not Turing complete as a result, and only when writing up a proof to demonstrate it as clearly as possible I discovered that even though I was correct that certain basic prime encoding operations couldn't be done directly with the PMMN commands, there were workarounds to get the same effect by rearranging the algorithm and using an effective jdecnz(r, z) instruction, which *can* be constructed using PMMN commands. The block termination bracket of while () {} is the *only* way to jump back in PMMN, but that can be used to create arbitrary jump-backs, and will work in a 2 register construction if non-destructive tests can be performed.... anyway, I now believe 2 register PMMN *is* Turing complete, but probably requires a proof to demonstrate how, because I don't think it's obvious, nor is the conversion trivial. I've lost some steam on that because it's not as dramatic as proving the 2 register version is *NOT* TC (I'm claiming 2 register Szewczyk notation for Minsky machine is not TC, but that's a more straightforward case -- PMMN was harder to reason about). I've digressed a bit, but the point is the non-destructive jump test is what made me realise jdecnz(r, z) is more powerful than the alternative, and allows that two instruction, 2 register set to be TC, and clearly Incdecisive Machine too.

On my Counter Machine Net Notation page I've added constructions which simulate (are?) the two Incdecisive Machine instructions, and the last two cells use those to simulate the 2 register, 2 instruction Turing complete set { inc(r), jdecnz(r, z) }. Not sure if that's too esoteric a notation to count as a 'proof', but it has me convinced. I'm working with CMNN using pen a paper to analyse these things and finding it very helpful. The ASCII / Unicode conversion is a bit of a pain, but I'm using that page as a reference 'zoo' for different constructs. Salpynx (talk) 07:51, 23 September 2022 (UTC)

Thanks for adding Incdecisive Machine to the list but I'm afraid your current notation isn't able to describe it properly. You see, incjnz is not right; after the register is increased it will always be non-zero for either case, and what Incdecisive Machine is really checking is if the new value is 1 (which meant it was 0 before increasing). So I would simply make this incjno (where z was replaced with o for one), 'increase-and-jump-if-not-one'. That's the best one I can think of, unless the notation is changed/extended some way.

I thought of is as "increase, jump-if-not-zero". The 'comma then' was supposed to emphasise the increase was unconditional, and only the jump was based on the register value, but I neglected to indicate it was the previous value. Increase, then jump-if-wasn't-zero might also work -- incjwz, but is also a bit unwieldy, but it was how I was thinking about it originally. I worried I had misunderstood the operation, but I think my diagrams are still good, it was just clumsy with the mnemonic wording. incjno is growing on me. Salpynx (talk) 09:30, 23 September 2022 (UTC)