Talk:Brainpocalypse

Some thoughts

First of all, once again I'm amazed. It seems to be a golden age of minimalization at the moment; another 2-instruction 2-character Turing-complete language (in its minimalization). Why is it happening now? (Not a rhetorical question!) Do you feel some kind of breakthrough/enlightenment or 'risen to another level' in your thinking of computation, or is it because knowledge of systems has accumulated enough which then has led to certain new ideas which have led to even more? I feel like I can't keep up with the progress any longer and it's giving me almost existential agony.

Anyhow! (1) The specification leaves halting undefined, as far as I can see. I assume it's like in brainfuck and Subtractpocalypse -- going past the last instruction halts the program. Would be worth mentioning on the page if so.

(2) My intuition (which often is wrong) tells me that there might be a more 'natural' Turing-completeness translation. Perhaps something much like my MM to Subtractpocalypse, but directly from Subtractpocalypse to Brainpocalypse. It's worth mentioning that because the MM-to-Sub translation keeps all the registers initially 0, this Sub-to-Brain translation would not need to care about register initialization either -- it's enough that it can translate just the MM-to-Sub subset of all possible Subtractpocalypse programs. I can imagine it using the same methods; treating each Subtractpocalypse command as a group of instructions that need to succeed, setting special register(s) after completing each addition or subtraction in a simulated command, correcting previously modified registers as it progresses... It might be very similar. (And who knows, possibly more complicated than the Waterwall method after all, I'm not sure because I don't understand that one yet.) I might get back to this...

(3) All that being said... If for some reason one wants to translate Subtractpocalypse to Brainpocalypse right now in a complex way: translate Sub to MM, MM to Waterfall, Waterfall to Brain. Translating Subtractpocalypse to MM is simple -- I'll add a method on the Subtractpocalypse page. --Keymaker (talk) 09:59, 14 June 2018 (UTC)

"Why is it happening now?" – I think what's starting to happen is that we're building up a collection of very simple languages that give a better indication of where the boundaries of Turing-completeness are than we previously had. In the past we could struggle for weeks to work out if something is Turing-complete, but nowadays it's often pretty easy to look at a language and think "that embeds the I/D machine" or "that embeds a Waterfall Model variant". I guess practice has helped me in particular, too; in 2016 I had no idea how to get anywhere with Three Star Programmer, by late 2017 I'd had an idea and figured it out, and now in 2018 I'd actually consider that a fairly easy language to prove Turing-complete, because the general ideas used there are also usable in a lot of other contexts.

A somewhat different answer to the same question: once I had the idea, (the non-minimised version of) this language took about ten seconds to create (there's only one reasonable way to merge brainfuck with Subtractpocalypse). I was inspired by recent edits to the BF instruction minimalization page (specifically, someone had tried to merge [ and ] into a single instruction by banning nested loops, which of course doesn't work for TCness as it can't do control flow within an infinite loop, so it got me thinking about what single control flow primitive could work without caring about anything other than zeroness or nonzeroness). Minimalizing it from there was fairly obvious given that I was looking at the minimalization page at the time! So this language wasn't really an intentional part of any big project or the like; it was a chance opportunity. I guess we're just getting better at exploiting the chance opportunities when they happen.

1. Fixed.
2. Compiling from Subtractpocalypse is *almost* very easy; it's one of the first things I tried. However, there are a few points where I got stuck (for example, there doesn't seem to be any simpler way to get the initial state and IP under control than in the existing construction). The largest problem is that restarting with a - always leaves the restarting cell at 0, and writing a Subtractpocalypse program to handle that restriction basically gives you The Waterfall Model anyway. Come to think of it, what we end up with is basically a The Amnesiac From Minsk variant in which we mostly forget not only what we were doing before a counter zeroed, but also which counter it is. That can't be TC without storing some additional state; in the construction here, you do it via exploiting the fact that the tape pointer is in a different place (so that you can start by blindly adding 6 to it and them compensating later, giving you something observable to record the fact). In a construction from Subtractpocalypse, it's unclear what would substitute for this.
3. Right, these languages are all playing around in a similar space. There's probably some way to optimise the translation but probably not as far as we'd like. --ais523 16:10, 14 June 2018 (UTC)

Number of cells

Is brainpocalypse TC with only 3 or 2 cells of unbounded integers, or infinite cells of binary bits? --None1 (talk) 09:45, 22 September 2023 (UTC)