Yesterday, I stuck in the internet with this article about programming language called BrainFuck
.
http://www.muppetlabs.com/~breadbox/bf/
So what is wonder me is this
Brainfuck is the ungodly creation of Urban Müller, whose goal was apparently
to create a Turing-complete language for which he could write the smallest
compiler ever, for the Amiga OS 2.0. His compiler was 240 bytes in size.
(Though he improved upon this later -- he informed me at one point that
he had managed to bring it under 200 bytes.)
So, is it smallest compiler of Turing-complete programming languages really today? And is it proven that smaller compiler doesn't exist anyway?
Is there any results in this area. It's really interested me, is there any smallest value of size of Turing-complete programming language's compiller and what is that value?
The size of the smallest possible BrainFuck compiler is totaly machine dependant. Therefore, if you speak about a certain value you must always consider the architecture it is running on.
The smallest possible BrainFuck compiler is 0bytes
The architecture this compiler is running on, has the neat property of beeing able to interpret Brainfuck Sourcecode natively. It has the even neater property, that a programs output resides at the same memory locations as its input does.
The byte code of the smallest posssible BrainFuck Compiler is then: "". Since this program terminates immediately, it does not apply any modifications to the input. Therefore the output of a run from this program always equals the input from this run. Since the architecure can execute BrainFuck natively, this program turns BrainFuck Sourcecode into binary code for this architecture. The program is therefore a BrainFuck compiler for this architecture.
Real Word Architectures
Unfortunetly the architecture described above is not applicable to real world applications, but neither is BraickFuck.