(an exploration into the murky underworld of Computer Science and Programming Languages)
The language 'brainfuck' knows the following commands:
| Cmd | Effect | Equivalent in C |
|---|---|---|
| + | Increases element under pointer | array[p]++; |
| - | Decrases element under pointer | array[p]--; |
| > | Increases pointer | p++; |
| < | Decreases pointer | p--; |
| [ | Starts loop, counter under pointer | while(array[p]) { |
| ] | Indicates end of loop | } |
| . | Outputs ASCII code under pointer | putchar(array[p]); |
| , | Reads char and stores ASCII under ptr | array[p]=getchar(); |
All other characters are ignored. The 30000 array elements and p are being initialized to zero at the beginning. Now while this seems to be a pretty useless language, it can be proven that it can compute every solvable mathematical problem (if we ignore the array size limit and the executable size limit).
more?
Actually, it's Turing-complete even if the executable size is limited to, say, half a K of source code. See http://www.hevanet.com/cristofd/brainfuck/brainfuck.html#turing and related pages.