Smallest compiler possible in a turing complete language?

Question

Brainfuck is known for its extremely small compilers. I have a VERY small device that probably couldn't fit even the smallest of brainfuck compilers in its data. Is there an esoteric programming language that has even smaller compilers than brainfuck AND is a turing complete language? This is getting old, but feel free to still bring in your own answers, I will be checking

Answer 1

I looked at the size of the Brainfuck compiler (~240 bytes in it's original form) and I doubt you're going to get smaller than that, it was designed to produce the smallest possible compiler (admittedly many years ago).

Although, from Wikipedia:

Except for its two I/O commands, brainfuck is a minor variation of the formal programming language P′′ created by Corrado Böhm in 1964. In fact, using six symbols equivalent to the respective brainfuck commands +, -, <, >, [, ], Böhm provided an explicit program for each of the basic functions that together serve to compute any computable function. So in a very real sense, the first "brainfuck" programs appear in Böhm's 1964 paper – and they were programs sufficient to prove Turing-completeness.

From the P'' page:

P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete.

So a compiler for P'', or a altered version of brainfuck that's equivalent, would be smaller and still turning complete.

However, if I don't follow the spirit of the question then the devices native instruction set will be Turing complete. An assembler will probably be too big but you could directly write the opcode values either into an executable file or a text file that is 'compiled' to an executable. That 'compiler' would probably be smaller. Although it's not a compiler in any real sense of the word, hence not following the spirit of the question.

Is this a real world question? If you don't have space for the compiler then where are your source and binaries going to go?

Related Question: What is the *conceptually* smallest *compiler* that can compile itself?

Answer 2

I have found the smallest BF compiler expressed using lambda expressions in a Binary form (BLC).

The interpreter is exactly 112 bytes (which is iirc. the exact amount of bytes for the Hello World program in BF itself).

Answer 3

MiniMAX

MiniMAX specification

Here is a complete DOS .COM executable interpreter for MiniMAX:

MOV SI,010E  # 3 bytes; 010E is the byte after the RET line
MOV DI,SI    # 2 bytes
MainLoop:    # assembler directive, 0 bytes
MOVSW        # 1 byte
LODSW        # 1 byte
ADD SI,AX    # 2 bytes
XCHG SI,DI   # 2 bytes
JNZ MainLoop # 2 bytes
RET          # 1 byte
<append program to interpret here>
             # Total: 14 bytes

Your device probably doesn't have exactly the same instruction set, but I can't imagine it being so very different. Probably less than 20 bytes still.

The downside is that MiniMAX programs that do anything useful are quite long, but if your only goal is to fit a TC interpreter on the chip, this'll do it for you.