Talk:Archway

Computational Class of Archway1

So, I'm around 20 years late here, but although this article seems to imply otherwise, Archway1 is actually Turing complete. This is easy to prove once you realize that Archway1 is actually reversible (aside from its irreversible input instruction), and that, rather than using it to simulate Brainfuck, you should instead use it to simulate Reversible Brainfuck.

I will give a simplified version of the proof, proving that a version of Archway1 that uses 1-bit memory cells can simulate Reversible Bitfuck (because this makes negating conditionals simpler) but the same thing can be accomplished with larger memory cells by using additional interleaved memory cells as temporary storage for computing the logical negations of memory cells (you can't logically negate an integer in-place with larger memory cells in a reversible programming language, because there are more non-zero values than zero values) or by using each 8-bit cell as a single "bit" and "negating" it with 128 +s.

In this 1-Bit Archway1, * toggles the current bit, as in Reversible Bitfuck. /, \, < and > function as in normal Archway1 (with > and < coincidentally overlapping in their role in both languages).

With *, <, and > already covered, in order to transform a Reversible Bitfuck program into a 1-Bit Archway1 program, all we have to do is replace every instance of (abcdef) (where abcdef is any set of instructions enclosed by parentheses) with:

                  / \      / \
                    *      *
                  \*/abcdef\*/
-> enter here    *\*/      \*/*   exit here ->
                    *      *
                    \      /
                  \          /

If the condition is initially 0, the code pointer will get bounced along the bottom rim and skip the entire loop. If it is initially 1, then the code pointer will enter the loop; it's probably easier to just trace through the interior of the loop yourself than to interpret any kind of description, but one key point to keep in mind is that the diamond shapes in the top left and top right are each a sort of "unconditional reflector" structure; either the entry reflector is active and reflects the code pointer or it's inactive and the code pointer enters the diamond and gets ejected along the same trajectory anyways. When the code pointer exits the body, if the condition has flipped to 0, then it bounces backwards along the inner lower rim and repeats the body.

I have read the description of the wire-crossing problem, and don't really understand what it is attempting to address, so I don't know if this construction satisfies what the language was originally intended to prove (no paths of the looping construct cross, except at explicit branching points, for what that's worth). But, the esolang file entry claims that the language is not even Turing complete, so I thought it would be worth correcting. But, it's kind of unclear where to make the edit, since this wiki article is basically the Archway2 article, even though it's just called "Archway", and the original Archway is just mentioned as a footnote. ImOnlyHereForReversibleComputing (talk) 00:08, 6 December 2025 (UTC)

This seems reasonable. On the subject of the wire-crossing problem, it was studied a lot in the early history of esolangs but I suspect it eventually turned out to be ill-defined (and to have somewhat unsatisfying trivial solutions with most reasonable definitions). The basic problem is that it is usually possible to implement a wire-crossing even in languages which don't have one, via using your data storage as a temporary to work out which way the program was going.

As for the article, the two options I can think of are either a) separate each section into Archway1 and Archway2 subsections, or b) create separate articles for Archway1 and Archway2. I think either of them would work and am not immediately sure which would be better (although recent practice on the wiki seems to have been to create as many pages as possible, I'm not sure I agree with it). --ais523 00:27, 6 December 2025 (UTC)