Expload

Expload is an esoteric programming language designed by Chris Pressey at the start of December 2012. It is an Underload derivative where programs cannot be guaranteed to be executed efficiently because individual instructions are selected for execution based on EXPTIME-complete problem instances.

Basing the language on Underload was done in the hope that a quining-based language would prevent an execution strategy that caches the results of previously-seen commands to speed up execution. Since the "next part" of the program is constructed and appended, successively more complex (or at least, never-seen-before-by-the-interpreter) problem instances can be constructed during program execution.

Description

Turmoids

An Expload program consists of a sequence of things we shall call turmoids. A turmoid is composed of the following symbols: "0", "1", ",", "|", ":" with the following (EBNF) grammar:

Turmoid ::= State {"|" State} ":" Number ",".
Number  ::= ("0" | "1") {"0" | "1"}.
State   ::= Branch "," Branch.
Branch  ::= ("0" | "1") ("0" | "1") Number.

A Number describes a binary number, for example 101 means 5.

Each State describes a possible state of a Turing machine. It consists of two branches. When in this state, the first branch is executed if the symbol on the tape is 0, the second if it is 1.

Each branch begins with a digit, which is the digit that will be written to the tape. The next digit determines if the head will move left (0) or right (1). The rest of the digits make a number, which is the state the TM will transition to after this branch. The number refers to the index of the state given by the order they are defined (0 = the first state defined in the turmoid, 1 = the second, etc.) If the TM transitions to any state which is not defined in the turmoid, it enters a halted state and stays there.

Finally, after all the states, a number is given, after a colon. This number is called b, and is used in the question given below.

Turmoids support one operation, resolving. To resolve a turmoid, the question "After b steps, is the TM in this turmoid in a halted state?" is asked. If the answer is "yes", the turmoid resolves to 1, else it resolves to 0. In the context of this question, the TM's tape is initially all zeroes, and the TM starts in state 0.

Resolving a turmoid is an EXPTIME-complete problem.

Instructions

The state of an Expload program is a stack of strings over the same set of symbols that make up turmoids.

To actually execute an instruction in Expload, three turmoids must be given. If there are fewer than three turmoids remaining in the program, or any turmoid is malformed, the program just halts.

The three turmoids are resolved to a string of 3 bits (leftmost turmoid = leftmost bit.) This string is then looked up in the following table:

000 - Swap the top two elements of the stack.  (Underload's "~")
001 - Duplicate the top element of the stack.  (Underload's ":")
010 - Discard the top element of the stack.   (Underload's "!")
011 - Concatenate the top element of the stack to the end of the second element of the stack.  (Underload's "*")
100 - Pop the stack and append that string to the program.  (Underload's "^")
101 - Push the string "0" onto the stack.
110 - If the string on the stack is a single character, increment it cyclically through the ordered set {"0", "1", ",", "|", ":"}
111 - Pop the stack and print that string.  (Underload's "S")

Computational class

Expload programs can be translated to Underload instructions fairly easily. However instead of () one uses 101 and 110 and 011 to build new strings on the stack. This may or may not be an obstacle; I haven't checked it fully.

Variations

Son of Expload

Instead of a series of turmoids, a single Turing machine is given at the start of the program:

TuringMachine ::= State {"|" State} ":".

The rest of the program consists of noombers, which are numbers written in binary, followed by colons:

Noomber ::= {"0" | "1"} ":".

Each noomber n supports one operation, reduction. Reducing a noomber asks the question "What symbol is under the TM's tape head after n steps?" and yields that symbol. (The TM does not retain any state between reductions of noombers; it "starts fresh" with a tape full of 0's, and in state 0, each time a number is reduced.) As with resolving of turmoids, reduction of noombers is EXPTIME-complete.

As above, sequences of three noombers are reduced to strings of three bits, and the operation is looked up on the table. However there is one straightforward modification of the table:

110 - If the string on the stack is a single character, increment it cyclically through the ordered set {"0", "1", ":"}

In addition, the following rule applies during program execution: each noomber reduced must be strictly greater than any previous noomber reduced. Otherwise the program just halts.

The computational class of Son of Expload is not known. Any Son of Expload program can be reduced to an Expload program simply by replacing each number n with a turmoid that contains the initial TM and whose b is n. However, reducing other languages to Son of Expload would be more difficult, due to the strictly-increasing-noombers rule.

Old Army Buddy of Expload

Instead of turmoids, the program consists of a sequence of Turing machines (as defined in Son of Expload.) However, only one Turing machine is needed to define an instruction. The number of steps h it takes for the Turing machine to enter the halted state is determined (possibly by simulating the Turing machine, but this is not necessarily the only method.) In this determination, the Turing machine is considered to start with a tape of all 0's, and in state 0. The following table is consulted, and the instruction which has the largest number in the "number" column, without exceeding h, is selected and applied.

0 - Swap the top two elements of the stack.  (Underload's "~")
128 - Duplicate the top element of the stack.  (Underload's ":")
256 - Discard the top element of the stack.   (Underload's "!")
512 - Concatenate the top element of the stack to the end of the second element of the stack.  (Underload's "*")
1024 - Pop the stack and append that string to the program.  (Underload's "^")
2048 - Push the string "0" onto the stack.
4096 - If the string on the stack is a single character, increment it cyclically through the ordered set {"0", "1", ",", "|", ":"}
8192 - Pop the stack and print that string.  (Underload's "S")

In addition, every 5 times the instruction corresponding to Underload's "^" is executed, all of the numbers in this table are doubled. Note that determining h still takes exponential time, but it is now time exponential in the size of the table. It is not necessary to solve the Halting problem for the Turing machine being simulated; if it has not halted in the number of steps assigned to the instruction corresponding to Underload's "S" (initially 8192), it must indicate that instruction.