Talk:I/D machine Turing-completeness proof

I wish Errorbucket had its own page, because I genuinely want to try and use to for something different --Yayimhere2(school) (talk) 16:36, 7 November 2025 (UTC)

You can use it for something different even without giving it its own page! You can just link to the proof page to give a definition of the language. Whether something is an esolang or not isn't defined by whether or not it has an esolangs.org article. --ais523 16:39, 7 November 2025 (UTC)

true, actually. well then, ill go try and make something with this, perhaps even a variant of it:] I'd rlly like to know, btw, how you came up with error bucket, because its quite the strange language to me(which is why I find it interesting as well) --Yayimhere2(school) (talk) 13:08, 24 November 2025 (UTC)

It's a case of first working out approximately what the language is like. In this case, the I/D machine doesn't have control flow, so I needed to think about how to emulate control flow in a language that doesn't have it, and one standard way to do this in esolangs is to have two data structures and operate on one or the other depending on the result of a check. That way, you can effectively skip blocks of code based on a condition by having them conditionally operate either on the data structure that your program is storing its data in, or on a data structure whose contents don't matter (see bit bucket for more information). That lead me to create a simple language with two data structures, one of which was write-only, and the obvious data structure was a queue (because the I/D machine can't move pointers to the left, only to the right, and queues are quite powerful and can be implemented even under that restriction). That simple original language was easy enough to prove Turing-complete – I used cyclic tag for that because it's good at proving queue-based languages Turing-complete, even if they're bad at control flow.

From that point on, it was a case of repeatedly changing the language to make it easier to implement in the I/D machine, but picking only changes that could easily be worked into its Turing-completeness proof. For example, the simple language started with just "data" and "bucket" as queue elements, but that can't be implemented directly in the I/D machine because the machine pointer gets stuck in a loop ("data" wants to be represented as a pointer to the pointer that points to the end of the data queue, and likewise for "bucket", but then a D command would always move between the end of a queue and a pointer to the end of a queue, which would make it impossible to leave the queues in a valid state because any situation in which the machine pointer moved away from the end of a queue would imply that the queue contained something else other than "data" and "bucket"). As such, I had to split "data" and "bucket" into active and inactive versions: the inactive versions just point to cells with known values so that they can be used to move the machine pointer elsewhere, and the active versions point to their "correct" locations so that they can be used to push onto the queue.

After that, the language mostly worked, but I had to make program startup work correctly. This was a case of working out what sequence of commands would set up the tape correctly, then working out what those commands would do from the point of view of the intermediate language. It turns out that they did something that was almost representable in the intermediate language, but one element of the queue would get corrupted, so I added an "error" option for queue elements (to represent the corrupted element) – leading to the full version ErrorBucket – and then proved that it was still Turing-complete because you could write programs in such a way that the error never ended up mattering. (Often making the startup work is the hardest part of compiling esolangs, because the language's "natural" startup state is often different from the state you want to maintain during the program, and many esolangs don't have enough control flow ability to run the startup code only once and then run the program's main loop repeatedly. So often you end up running the startup code unconditionally and then attempting to undo its effects. The usual trick is to come up with some code that "pre-undoes" the startup code, i.e. if you run it immediately before the startup code the combination does nothing, and then put that code at the end of the main loop so that you can put the startup code at the start, and it effectively only runs once. But in this case, it was easier to undo the effect of the startup code using ErrorBucket code than I/D machine code.) --ais523 14:07, 24 November 2025 (UTC)

Oh, thats really cool! I hadn't realized the error was an unusable element. But yea, thats really cool!!! :] --Yayimhere2(school) (talk) 15:26, 24 November 2025 (UTC)