|Computational class||Turing complete|
|Reference implementation||See below|
Aubergine is a minimalist language with 4 instructions, 4 variables, and a single constant, created by User:Boily in 2008.
- 1 General syntax
- 2 Variables
- 3 Instructions
- 4 Examples
- 5 Computational Class
- 6 Implementations
An Aubergine program mixes instructions and data in the same space, as a list of integers. Before execution by an interpreter, the script is split character-wise, then their ASCII integer value is taken.
Each cell can hold any integer value, even negative ones.
Instructions consist of three consecutive integers, where the first indicates which kind of instruction is to be executed, and the rest tells what is to be manipulated.
a and b
"a" and "b" are two multi-purpose variables. They initially are set to zero.
These variables can be used as pointers. When written "A" and "B", they point to cells in the program space. For example: if a equals 3, then A equals the integer at the program's fourth space. If a is negative or greater than the length of the program, using A is a fatal error.
The letter "i" represents the instruction pointer. It is automatically incremented by 3 after every instruction execution. Initially, "i" equals zero, which is also the first program cell.
You can use "i" in the same manner as "a" and "b". Note that there is no indirection with "i", i.e. "I" is not valid.
"o" -- short for Outside -- is only valid with the assignment instruction. When used as first parameter, it outputs an integer converted to a character to the screen. As a second parameter, it inputs a single character converted to an integer.
The "1" constant returns the integer 1. It cannot be used as an instruction's first parameter!
Equal (=) puts the second parameter's value into the first parameter.
Putting either a negative value, or one which is greater than the program's length, into "i" halts the program without error.
Plus (+) increments the first parameter by the second parameter's value.
Minus (-) acts as plus, but decrements the first parameter.
Colon (:) is a conditional jump. If the second parameter's value is different from zero, then the instruction pointer is set to the value of the first parameter. Otherwise, it does nothing.
Even if the jump was successful, "i" is still incremented by 3 after the instruction.
=aA-a1=oA=bi+b1-Ab-bb:bA+B1=iBGolf by Quintopia !dlroW ,olleH
(Ensure it is exactly 62 bytes long by adjusting the length of the non-code part in the middle before running it.)
The tab character at the end is part of the program. Be sure to copy it when testing this example.
Count up forever (in unary)
=A1+i1 =bi-b1-b1:Ba+b1=oB+A1=aA-a1-ii =oB-a1-ii
(Ensure it is exactly 61 bytes long by adjusting spaces in the middle before running it.)
If we take "each cell can hold any integer" to mean that the registers and program cells are unbounded, which seems quite reasonable, then we can translate any 2-register Minsky machine to an Aubergine program, showing that the language is therefore Turing-complete.
Turing-completeness proof sketch
(Note, the following is untested. There may very well be bugs in it.)
For concreteness, we will say that the instructions of our Minsky machine are:
INC R0 IF R0 == 0 THEN GOTO label ELSE DEC R0 INC R1 IF R1 == 0 THEN GOTO label ELSE DEC R1
The two registers of the Minsky machine (R0 and R1) will be stored at locations 0 and 1 in the program. Start the program with:
This sets R0 and R1 both initially to zero. (Just don't jump back to the beginning, because the initial
=A is now gone.) Then translate as follows:
IF R1 == 0 THEN GOTO <label> ELSE DEC R1is translated in two phases; first it becomes:
This puts g+249 into
a, where g is the location of the
:. If R1 is not zero, execution will continue at g+249. The space between g+6 and g+249, indicated by
...GOTO label... in the schema above, should be used to jump to the desired label. There will be 81 instructions' worth of space there to compute the label and jump to it, which should be plenty for most labels (and more room can be obtained simply by making the initial
a a bigger multiple of three.) For example, to jump unconditionally to location 33 (the 11th instruction), we can fill that
...GOTO label... gap with
padded with a sufficient number of spaces (or whatever else you like.)
IF R0 == 0 THEN GOTO label ELSE DEC R0is identical to its R1 counterpart, with
=b1-b1. (Also, the
...GOTO label...gap will be one instruction smaller.)