一個通用編程語言要做的最基本的就是圖靈完備，我們常用的語言的通用語言都是圖靈完備。那么為什么圖靈完備（Turing Complete）這么重要呢？

維基百科
在可計算性理論，如果一系列操作數(shù)據(jù)的規(guī)則（如指令集、編程語言、細(xì)胞自動機(jī)）可以用來模擬任何圖靈機(jī)，那么它是圖靈完備的。

那么問題來了，啥又是圖靈機(jī)呢。繼續(xù)維基百科

通俗而簡單的說法就是：一個處理器能不斷的處理輸入數(shù)據(jù)，并輸出數(shù)據(jù)，這個處理器維護(hù)一個有限狀態(tài)集，狀態(tài)集+數(shù)據(jù)對應(yīng)的結(jié)果是固定。

那么圖靈完備的通俗說法就是：能控制圖靈機(jī)完成所有功能的編程語言。

我們大名鼎鼎的編程語言C語言，當(dāng)然是圖靈完備的。但是我們今天要介紹一款神奇的編程語言，簡潔，關(guān)鍵字少，容易上手，關(guān)鍵是圖靈完備。要說缺點么，就是要實現(xiàn)功能，過于繁瑣了。

Brainfuck
它的默認(rèn)有狀態(tài)集：
一個以字節(jié)為單位、被初始化為零的數(shù)組、一個指向該數(shù)組的指針（初始時指向數(shù)組的第一個字節(jié)）、以及用于輸入輸出的兩個字節(jié)流。

能執(zhí)行的操作：

打印 hello world! (摘抄自wikipedia)

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

代碼很簡潔，但不是很那讀懂，非常燒腦。但是讀代碼可以倒過來看，不是要打印Hello World!嗎？打印字符用的是.，那么肯定要執(zhí)行至少12個.，實際上還有一個不可見字符換行符\n，總共執(zhí)行13個.。我們往代碼里面數(shù)，發(fā)現(xiàn)正好13個。那就可以倒推出來，第一個.打印的是H。依次類推，我們就能知道所有點對應(yīng)的字符是啥了。

下面給出從打印開始的，狀態(tài)集的狀態(tài)：

'.', arr: [00 48 64 1e 0a], ptr: 1 # print arr[1] 'H'
'>', arr: [00 48 64 1e 0a], ptr: 2
'+', arr: [00 48 65 1e 0a], ptr: 2
...
'.', arr: [00 57 64 21 0a], ptr: 4 # print arr[4] '\n'

c語言實現(xiàn)的解析器(簡單)：

typedef struct {
    char arr[1024];
    char ptr;
    void (*putc)(char* p);
    void (*getc)(char* p);
} BrainfuckStateSet;

void Brainfuck_putc(char* p) {
    putc(*p, stdout);
}

void Brainfuck_getc(char* p) {
    *p = (char)getc(stdin);
}

void Brainfuck_parser(BrainfuckStateSet* state, const char* code) {
    int codeIdx = 0;
    while (code[codeIdx]) {
        //printf("arr: [%02x %02x %02x %02x %02x %02x], ptr: %02x  ---- code: %4d: %c\n", state->arr[0], state->arr[1], state->arr[2], state->arr[3], state->arr[4], state->arr[5], state->ptr, codeIdx, code[codeIdx]);
        switch (code[codeIdx]) {
        case '>':
            state->ptr++;
            break;
        case '<':
            state->ptr--;
            break;
        case '+':
            state->arr[state->ptr]++;
            break;
        case '-':
            state->arr[state->ptr]--;
            break;
        case '.':
            state->putc(&state->arr[state->ptr]);
            break;
        case ',':
            state->getc(&state->arr[state->ptr]);
            break;
        case '[':
            if (!state->arr[state->ptr]) {
                while (code[codeIdx] != ']') codeIdx++;
            }
            break;
        case ']':
            if (state->arr[state->ptr]) {
                while (code[codeIdx] != '[') codeIdx--;
            }
            break;
        default:
            // nothing todo, ignore
            break;
        }
        codeIdx++;
    }
}

// print hello world use brainfuck
// simulate brainfuck
void Brainfuck_PrintHelloWorld() {
    // prepare state set
    BrainfuckStateSet state = {
        {0}, 0, Brainfuck_putc, Brainfuck_getc
    };
    memset(&state.arr, 0, 1024);


    // parser
    const char* code = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]"
        ">++.>+.+++++++..+++.>++.<<+++++++++++++++."
        ">.+++.------.--------.>+.>.";
    Brainfuck_parser(&state, code);
}

其實編程語言的三要素：順序執(zhí)行，條件判斷，循環(huán)（條件判斷+跳轉(zhuǎn)），其它都是輔助功能。