Talk:Black Turing-completeness proof

From Esolang
Jump to navigation Jump to search

Thank you for writing this! I think the major innovation here is the way the register works; it's much easier than mine.

Upon seeing your register construct, it struck me that it on its own might be enough to implement The Amnesiac From Minsk level 2, which is known to be Turing-complete. (In other words, we're using registers themselves as a substitute for flips.) Conceptually, what you have here is a register whose I/O structure is increment → incremented, decrement → decremented, and check → zero/nonzero. If you connect "decremented" to "check", you have exactly the structure of TAFMl2 (the "increment" and "decrement" inputs and "incremented" output are the same as in TAFMl2, with "zero" corresponding to "critical-decremented" and "nonzero" corresponding to "successful-decremented"). That said, the construction that goes via Exeter rather than TAFM is almost certainly more efficient, as a flip is less general than a counter and thus can be more self-contained (and the TAFMl2 construction uses a lot of counters to simulate the effect of just one flip). --ais523 22:28, 19 January 2018 (UTC)

For some reason I never understood TAFM before. (I understand at least the first level now.) If I had understood the language before, I would have remembered and utilized it. But I had neither memory nor understanding... (Insert unintentional amnesiac joke here.) Well, it's in my translation toolkit from now on! Implementing level 1 would have saved me much trouble - after all, I had to invent the flips and the pos/neg routes because I didn't see how registers could be enough. TAFM is quite brilliant, really... While I was shuffling my ideas, I was thinking of something vaguely like the level 1 but without the triggering (which probably is the very source of this language's power). But now I keep wondering if I was too hasty in thinking that my idea, extremely vague as it was, wouldn't work; I need to try again. (In terms of Turing-completeness, not Black translation.) TAFM (at least the level 1 that I'm now familiar with) has this interesting property, like Exeter (well, it would be bad if Exeter didn't have it, being designed for it), that they're quite fit to be translated into 2D. More interesting work to be done there. Anyway, I might make a TAFMl1-to-Black translation at some point (unless someone gets there before me) because - as I see it - there's different kind of value in a translation that is the simplest to generate, even if the present translation were (and I think it is) more efficient and resulted in shorter run-times... --Keymaker (talk) 17:54, 24 January 2018 (UTC)
Your construction has actually helped me understand the difference between TAFMl1 and TAFMl2.
If with your register, you connect "decremented" to "check" (i.e. decrement first, then check to see if you decremented to zero), you get TAFMl2. If, on the other hand, you connect "nonzero" to "decrement" (i.e. check first, and decrement only if nonzero), you get TAFMl1. So I guess that in a way, TAFMl2 isn't "simpler" (although it is harder to program in) – rather, it's simply a different model of how the counters behave, and either could be appropriate for a language.
In terms of "translated into 2D", TAFM wants to be translated into a nonlinear execution environment, but that doesn't necessarily have to be 2D; it could be graph-based, token-based (i.e. with the IP being an enum rather than a number), heavily dependent on GOTO statements, or the like. --ais523 09:24, 31 January 2018 (UTC)

"A good GUI interpreter for Black"

Hello! I'm hailing from the Conwaylife forums, where user '_zM' has noticed that Black is quite-tidily representable as a multi-state cellular automaton via the rule-table format used by Golly (a popular utility for exploring CA and such). Here's _zM's original post, and here (on gist) is my modification that assigns arrow icons where relevant to each cell state (indicating the direction in which the IP and/or non-spaces are moving) and fixes a small bug.

To use it, download Golly from SourceForge (you can also view its landing page) and open it. Next, simply copy to your clipboard the ruletable data, then move to a Golly window and hit Ctrl+V: this creates a file for the rule somewhere, letting it persist later on. Once the rule-file is created (the large colored info bar will turn purple with a small message saying "Created rule [...]/rules/Black.rule"), note the presence (at the grey bar's right-ish side) of a single digit with two square icons next to it. Click the rightmost of these two icons; this'll force the cells/instructions to display with their arrow-symbol icons rather than as monocolored blocks.

And that's it! To edit a Black program like this, click on "State: 1" in the row of icons to allow your mouse to place non-space instructions, and use any of states 2 through 5 to place an accordingly-oriented instruction pointer. (Note: an interesting quirk of this implementation is that it allows more than one instruction pointer to be placed on the same grid at once.) Press C to change your mouse cursor, and when it takes the shape of a crosshair you can use it to select a pattern; once something is selected, use Ctrl+C/Ctrl+V to copy/paste it, X and Y to mirror it along the respective axis, and Shift + , or Shift + . to rotate.

Golly of course wasn't made specifically for this, so it has a bunch of features that aren't quite necessary for it to act as a Black interpreter, but I do believe it's an adequate solution!

Wright (talk) 07:40, 15 February 2018 (UTC)

Thanks for posting this. I added links to this interpreter on the main Black page. --ais523 00:28, 5 June 2018 (UTC)
Just saw this, thank you in turn :) I updated the description of my Gist accordingly. Wright (talk) 03:41, 3 October 2018 (UTC)