Along and Across
Along and Across is a family of esoteric programming languages created by User:ais523 in 2018. (Alternatively, it can be seen as a single metalanguage which takes two languages as input and produces a language as output.) The idea behind the language is to explore the definition of Turing-completeness, especially in the case of "across" languages that require an infinitely long input to run.
Syntax
A specific language in the Along and Across family consists of a pair of languages (the "along" language and the "across" language). A program in such a language is a pair, consisting of a program in the "along" language and a program in the "across" language. (It may be that the two languages are the same, but in this case, the "along" program and the "across" program are still identified with specific roles).
The "along" language must take a finite sequence of bits as input, and produce one of a finite number of possible values as output. (These are known as "symbols"; the set of symbols is fixed by the choice of along and across languages.)
The "across" language must (lazily) take an infinite sequence of symbols as input. It produces no output other than its halt behaviour. (Think of the "across" language as reading the first input symbol and then deciding whether to halt; if it doesn't, reading the second input symbol and then deciding whether to halt; and so on.)
Semantics
In order to execute an Along and Across program, the implementation starts by running the "along" program with the LSB-first binary expansion of the integer 1 (that is, 1) as its input. The output is given as input to the "across" program. Then a new "along" program execution is started but given the LSB-first binary expansion of the integer 2 (that is, 01) as its input; the output is given as input to the same execution of the "across" program. The execution continues with increasingly large integers (3, 4, 5, etc…) until the "across" program halts (possibly forever). If the "across" program does halt, so does the Along and Across program.
Computational class
ais523 conjectures that Along and Across can not be Turing-complete if both the "along" language and the "across" language use a bounded amount of memory. ais523 additionally conjectures that it cannot be Turing-complete if the "along" language uses a bounded amount of memory, and the "across" language is no-more powerful than a push-down automaton. Neither of these have been proven (but ais523 would be interested in a proof or counterexample to either).
Along and Across can, however, be Turing-complete if the "along" language is a push-down automaton and the "across" language is a finite-state machine. To see this, consider a string-rewriting based language like Thue; it's possible for a push-down automaton to, given two strings encoded as (the first string) concat (separator outside the alphabet of both strings) concat (the second string backwards) concat (separator outside the alphabet of both strings), determine whether the two strings could be consecutive steps of the internal state of a Thue program. In fact, you can design the push-down automaton to return to its original state if the input has the right format (and to lock itself into an error state otherwise), so it can check multiple such pairs at once. It's also trivial to discard the first and last strings in a list like this; so you can also design a push-down automaton that checks the remaining adjacent pairs that the first push-down automaton didn't. This means that given a variant of Thue which has an explicit halt state, and a specific program in that language, it's possible to design two push-down automata so that they can only both succeed on the same string if the string represents a halting execution of that Thue program. Now combine them into a single push-down automaton that consumes the first bit of its input string and runs one of the original two automata on the rest of the input string (using the value of the consumed bit to determine which to run), with three output states (failure, success starting from a 0, success starting from a 1). Use this as the "along" program. The "across" program now merely needs to look for "success starting from 0" and "success starting from 1" in sequence (with no intervening outputs). This will only be discovered if there's a halting execution of the Thue program, and will be discovered if there's a halting execution of the Thue program (at the position corresponding to twice the encoding of that execution, plus 1, as the input to the last two executions of the "along" program will have been 0 concat (the encoding of that execution) and 1 concat (the encoding of that execution)). So the "across" program – and thus the Along and Across program – will halt if and only if the Thue program can.