EXPBLARGL

EXPBLARGL is an esoteric programming language designed by Chris Pressey on or about February 21, 2015, with the goal of being Turing-complete, but where the mapping from Turing machines to EXPBLARGL programs is not computable in a reasonable time, even though EXPBLARGL programs are of reasonable length.

An EXPBLARGL program consists of a non-negative integer, given in decimal digits, followed by a space, followed by the text of a brainfuck (or, to accommodate people who can't stand brainfuck derivatives, Underload) program. (Detect which of brainfuck or Underload it is by looking at what symbols it contains; assume that if it contains only characters from the set +-><[]., it's brainfuck, else it's Underload.) In the following, this brainfuck-or-Underload program will be called P, and the leading non-negative integer will be called T.

To run an EXPBLARGL program, run P only if there are exactly T shorter programs which, when run for 2^(length of P) steps each, produce the same output as P. Otherwise, just stop.

Note that "shorter program" means "shorter program in L" where L is the language P is written in (brainfuck or Underload.)

Note also that, if P takes input, EXPBLARGL only needs to look for shorter programs which produce the same output as P on the given input, not all inputs. (i.e. we are not looking for shorter equivalents of P.)

While receptive to arguments to the contrary, Chris Pressey appears to believe that:

• EXPBLARGL is Turing-complete, because every Turing machine can be mapped to a brainfuck or Underload program (we know that both languages are Turing-complete), and every such program has some number of shorter programs which produce the same output in 2^(length of P) steps (even if that number is zero.)
• In order to find the EXPLBLARGL program corresponding to a given Turing machine, one must survey all the shorter programs to figure out what number to prefix P with.
• "Survey" might include using clever proofs of some sort, to rule out entire subsets of shorter programs, but
• it seems likely that there are cases where this surveying, regardless of how clever it is, is going to degrade into step-by-step simulation and thus take at least EXPTIME.
• Complexity theory has probably not yet determined the veracity of the previous bullet point.

Sketch of an EXPBLARGL interpreter:

make S an empty dictionary
read integer, and call this T (and discard space following it)
read characters until eof, call this P
determine if P is brainfuck or Underload
for each possible program smaller than P:
    simulate it for 2^(len P) steps
    increment S[its output]
simulate P
if it never terminates, fine, you never terminate
if it does terminate, check if its output is in S
if it is, and if T = S[its output], output its output.
if it is not, and if T = 0, output its output
end

History

It all started with ais523 thinking about an alternate way to formulate Turing-completeness. Something about being able to, given n, compile byte n of a program in O(1) time.

Chris noted this is the same as compiling the whole program in O(n) time (where n is the length of the program,) and that "dumb" (non-optimizing) compilers to and from most "reasonable" languages need not take more than O(n log n) time.

Challenge was implicitly proposed: find a language which requires more than O(n log n) time to compile a Turing machine to it.

int-e proposed "Encode each brainfuck program as an integer n and have the program text be the n'th Fibonacci number written in unary", which meets this goal.

Chris defined the first version of EXPBLARGL as an attempt at a stronger and more interesting language.

ais523 noted that not only is it inefficient to compile a TM to an EXPBLARGL program, it is also inefficient to run an EXPBLARGL program. Conjecture was floated: this is true in general, i.e. for any language X, if it takes (say) super-polynomial time to compile Turing machines to it, it takes super-polynomial time to run programs in it. This conjecture has not yet been proven or disproven.

A flaw was found in EXPBLARGL. The language was originally defined with a "Y" or "N", instead of an integer, at the start, where "Y" meant there was at least one shorter program, and "N" meant there wasn't. Unfortunately, it all falls apart that way, because the compiler can always artificially extend the program by adding e.g. +- to the front of it, then it knows there's a shorter program that produces the same output. The same can be said for looking for permutations -- the compiler can introduce a NOP that it knows can be permuted somewhere.

To make something that was at least stronger, Chris proposed taking int-e's construction and replacing "Fibonacci" with "Ackermann". vanila observed it need no longer be written in unary -- after all, what's log in the face of Ackermann?

Some discussion here about how this would fail Minsky's definition of Turing-completeness as he describes it in "Computation: Finite and Infinite Machines". (He suggests the mapping should be at most primitive recursive. The Ackermann function isn't.)

Then Chris "fixed" EXPBLARGL by replacing the is-there-a-shorter-program test with the count-the-shorter-programs-exactly test. Whether this new formulation can also be defeated by a sneaky compiler or not, has not yet been shown.