Intro

上篇文章中對圖靈機的討論是錯誤的，因為那篇文章中試圖去使用一個具體的機器去指代圖靈機，這會造成極大的誤解。
本文將會解決這些問題。

Tips:發(fā)現(xiàn)錯漏請指出，我盡力修改( ;′д`)

圖靈機

圖靈機的形式化定義如下

圖靈機是一個七元組(\(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject}\))其中\(Q,\Sigma,\Gamma\)都是有窮集合。

1. \(Q\)是狀態(tài)集
2. \(\Sigma\)是輸入字母表，不包括空白符號\(\sqcup\)
3. \(\Gamma\)是帶字母表，其中\(\sqcup \in \Gamma,\Sigma \subseteq\Gamma\)
4. \(\delta : Q \times \Gamma \to Q \times \Gamma \times \{L,R\}\)是轉(zhuǎn)移函數(shù)
5. \(q_0 \in Q\)是起始狀態(tài)
6. \(q_{accept} \in Q\)是接收狀態(tài)
7. \(q_{reject} \in Q\)是拒接狀態(tài)，并且\(q_{rejecct}\not ={q_{accept}}\)

圖靈機\(M\)的工作方式如下：

1. \(M\)接收方格帶上的輸入\(w = w_1w_2...w_n \in \Sigma^*\)，方格帶上除去\(w\)其余保持空白（填入空白符號）。
2. \(M\)開始運行，按轉(zhuǎn)移函數(shù)所描述的規(guī)則運行。如果讀寫頭在最左端試圖左移，則讀寫頭不動，其他照常運行。
3. 不斷運行直到\(M\)進入接收狀態(tài)或者拒絕狀態(tài)。
4. 如果最終\(M\)無法進入這兩種狀態(tài)，則M將永遠運行下去，不會停機。

圖靈機可以形式化描述，圖靈機的計算過程自然也能形式化描述。這需要引入一個新的概念——格局。

圖靈機計算過程中，將當前狀態(tài)、當前帶內(nèi)容與讀寫頭位置組合在一起，稱為圖靈機的格局。
格局常以特殊的方法表示，對于狀態(tài)\(q\)與當前帶上被讀寫頭分割的兩個字符串\(u\)和\(v\)，以\(uqv\)表示如下格局：
當前狀態(tài)是\(q\)，當前帶內(nèi)容是\(uv\)，讀寫頭當前的位置是\(v\)的第一個附后，帶上\(v\)的最后一個符號之后的符號都是空白符。

如果圖靈機能從格局\(C_1\)一步進入\(C_2\)，則稱格局\(C_1\)產(chǎn)生格局\(C_2\)
于是，對圖靈機計算進行形式化描述即為：

設(shè)\(a,b,c\)均為\(\Gamma\)中的符號，\(u\)和\(v\)是\(\Gamma^*\)中的字符串，\(q_i\)和\(q_j\)是狀態(tài)，則\(uaq_ibv\)和\(uq_jacv\)是兩個格局，如果轉(zhuǎn)移函數(shù)滿足\(\delta(q_i,b)=(q_j,c,L)\)則說：
\(uaq_ibv\)產(chǎn)生\(uq_jacv\)
上面是左移的情形，下面是右移的情形：
如果\(\delta(q_i,b)=(q_j,c,R)\)，則說
\(uaq_ibv\)產(chǎn)生\(uacq_iv\)
當讀寫頭處于左端點或者右端點時，這個情形會發(fā)生變化，
左端點下，左移是 \(q_ibv\)產(chǎn)生\(q_jcv\)，右移是 \(q_ibv\)產(chǎn)生\(cq_jv\)
右端點下，\(uaq_i\)等價于\(uaq_i\sqcup\)，這是由于假設(shè)了帶子上沒有描述的位置都是空白符，這樣就只需要正常處理就行了。

M在輸入\(w\)上的起始格局是\(q_0w\)，表示機器處在起始狀態(tài)，且讀寫頭在最左端。
處在接受狀態(tài)的格局是接受格局；處在拒絕狀態(tài)的格局是拒絕格局。
接受與拒絕狀態(tài)都是停機狀態(tài)，它們不產(chǎn)生新的格局。

于是我們形式化了圖靈機的工作方式。
此時一個確定的輸入\(w\)存在著一個確定的格局序列\(C_1,C_2,C_3...C_k\)。
如果格局序列滿足：

1. \(C_1\)是\(M\)在輸入\(w\)上的起始格局。
2. 每一個\(C_i\)產(chǎn)生\(C_{i+1}\)。
3. \(C_k\)是接受格局。

我們就認為M接受輸入\(w\)。
\(M\)接受的字符串的集合稱為M的語言，記作\(L(M)\)

如果一個語言能被某一圖靈機識別，則稱該語言是圖靈可識別的

我們可以很自然的想到，當圖靈機接收一個輸入，最終只會處在三種狀態(tài)：接受、拒絕、不停機。

于是，現(xiàn)在我們有了一個較為準確的對圖靈機的描述。

圖靈完備

眾所周知，想要證明一個系統(tǒng)是圖靈完備的，就需要使得它能模擬圖靈機的所有行為。

本部分思路來自Frans Faase；發(fā)現(xiàn)未知宏可參考Alva L. Couch的文章

brainfuck

依據(jù)前面的內(nèi)容我們不難發(fā)現(xiàn)，一臺確定的圖靈機\(M\)在接收一個確定的輸入\(w\)時，會產(chǎn)生一個確定的格局序列\(C_1,C_2,C_3...C_k\)

也就是說，圖靈機的運行，可以寫成一長串的格局序列。這意味著，只要能找到一個方法，讓brainfuck正確的表示出這一串格局序列，就能用brainfuck模擬圖靈機。

所以，我們需要找到一個辦法，來讓brainfuck可以描述出每一個格局。并實現(xiàn)格局到下一個格局的產(chǎn)生。

由前面的內(nèi)容我們可以知道，一個格局記錄3種信息：當前狀態(tài)、讀寫頭位置、當前帶內(nèi)容。

想用brainfuck來表達這些信息，先要做一些簡單的準備工作。
我們知道一臺圖靈機\(M=(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})\)。不難看出，一種圖靈機僅有兩種符號——\(狀態(tài) \in Q\)和\(符號 \in \Gamma\)

1. 先映射\(\Gamma\)到自然數(shù)\(0\) ~ \(n-1\)，\(n\)為符號數(shù)。特別的，先將空白符\(\sqcup\)映射到\(0\)，記作\(\sqcup \to 0\)。
2. 再映射\(Q\)到自然數(shù)\(0\) ~ \(m-1\)，\(m\)為狀態(tài)數(shù)。特別的，\(q_0 \to 0;q_{accept} \to 1;q_{reject} \to 2;\)。

這樣，我們就能用數(shù)字來表達圖靈機的全部符號了。
于是乎，我們可以開始用brainfuck來表示格局了。
當前帶內(nèi)容可以是是無限的，但是沒關(guān)系，brainfuck能操作的數(shù)組也是無限長的。但很快我們就發(fā)現(xiàn)了，brainfuck的指針并不能儲存狀態(tài)。我們將不得不將一些額外的信息儲存在數(shù)組上，并且，brainfuck想要對數(shù)據(jù)進行操作，幾乎不可避免地需要一些額外的空間，但brainfuck只有一個數(shù)組。好在它是無限長的，就如希爾伯特所提出的無限旅館問題那樣，我們的這個數(shù)組完全足夠。

我們規(guī)定數(shù)組的一第個位置用于儲存狀態(tài)，第二個位置用于儲存讀寫頭位置，第三個位置用來儲存讀寫頭當前指向的字符，第四個位置用來作為新狀態(tài)的臨時儲存，第五個位置用來做新的讀寫頭位置的臨時儲存，第六個位置用來做新字符的臨時儲存。
并且，由于brainfuck對數(shù)據(jù)的操作需要一些額外的空間，所以我們額外分配五個位置做臨時存儲位置。
后續(xù)的數(shù)組便用來存儲當前帶上的字符串。
所以，我們的數(shù)組是這樣的

我們規(guī)定數(shù)組前面的部分（0~10）為操作區(qū)，后續(xù)部分為紙帶區(qū)。

brainfuck宏

brainfuck的可讀性并不好，所以我們需要一些宏，用來提高可讀性。

# 首先我們需要一個用來尋址的宏to()，它將展開成多個`<>`，能精確地移動到正確的位置。
# 并且我們規(guī)定這個宏只能用在操作區(qū)與紙帶的第一個位置tape0之間的移動。


# 用to()給循環(huán)指定判斷位置[]
for(x) = to(X)[;
next(x) = to(X)-];

# 用to()精確操作數(shù)
dec(x) = to(x)-;
inc(x) = to(x)+;

# 將s上的數(shù)字移動到d。 
move(s,d) = to(s) [ to(d) + to(s) - ];

# 如何拷貝呢？移動不只可以執(zhí)行一次。
move2(s,d1,d2)= {
	for(s)
		to(d1) +
		to(d2) +
	next(s)
	}

copy(s,d,t) = move2(s,d,t) move(t,s);

# [條件判斷是brainfuck唯一的條件判斷，我們需要讓它變得更加好用一點。

# 首先我們需要一個可以在任意位置寫入0的宏。
zero(a) = to(a) [-];

# 于是現(xiàn)在有條件判斷了。
if(a) = to(a) [;
endif(a) = zero(a) ];

ifelse(a,t) = inc(t) if(a) dec(t);
else(a,t) = endif(a) if(t);
endelse(t) = endif(t);

# 由于[是一個零跳轉(zhuǎn)，所以我們很自然的認為0是False，而其余的數(shù)則是True，于是可以有邏輯運算
# 值得注意的是，三種邏輯操作都會使得原操作數(shù)被清零。s是被操作的數(shù)，d是結(jié)果輸出的位置。
or(s1,s2,d) = move(s1,d) move(s2,d);
and(s1,s2,d) = if(s1) move(s2,d) endif(s1) zero(s2);
not(s,d) = inc(d) if(s) dec(d) endif(s);

# 與常數(shù)比較
# 與零比較，其實就是進行not()操作，至于其他的數(shù)？1-1=0,2-1=1...
isZero(s,d) = not(s,d);
isOne(s,d) = if(s) dec(s) isZero(s,d) endif(s);
isTwo(s,d) = if(s) dec(s) isOne(s,d) endif(s);
isThree(s,d) = if(s) dec(s) isTwo(s,d) endif(s);
....

# 圖靈機運行就是不斷產(chǎn)生新格局的過程，所以我們還需要另一個循環(huán)——while
while(X) = to(X)[;
wend(X)  = to(X)];

# 接下來要處理讀寫頭的讀寫操作，我們需要新的移動宏，用來移動到紙帶上。
# 這是兩個特殊的宏，它只有在輸入被確定后才替換。
# {(*head)*>}意思是寫入head位置儲存的值相等數(shù)量的'>'，后面的同理
totape() = to(tape0){(*head)*>};
back() = {(*head)*<}

# 獲取/寫入字符
# 其實這是一個改寫過的copy()，將紙帶上對應(yīng)的符號復(fù)制到操作區(qū)里。
getsymbol(x,t1) ={
	totape()[
		back()
		to(d1) +
		back()
		to(d2) +
	totape()-]
	back()
	to(t1) [ totape() + back()to(t1) - ]
}

setsymbol(x) ={
	totape()
	[-]
	back()
	to(x) [ totape() + back()to(x) - ]
}
;

brainfuck is Turing complete

將指針位置存放在操作區(qū)，僅在讀寫紙帶時前往紙帶區(qū)。

依據(jù)上面所給的規(guī)定，我們來處理程序的主體部分。
它做了5件事：

1. 判斷是否停機
2. 讀取字符
3. 按照轉(zhuǎn)移函數(shù)產(chǎn)生一個新格局
4. 寫入更改
5. 循環(huán)回到開頭

IsOne(state,t1)
IsTwo(state,t2)
and(t1,t2,t3)
not(t3,t1)
while(t1)

getsymbol(cursymbol,t1)

/***map***/

setsymbol(newsymbol)

zero(cursymbol)
zero(head) move(newhead,head,t1)
zero(state) move(newstate,state,t1)

IsOne(state,t1)
IsTwo(state,t2)
and(t1,t2,t3)
not(t3,t1)
wend(t1)

接下來我們需要給每一個\(\delta\)定義一個映射函數(shù)
我們定義一個映射模板map。它在接受輸入后，與自身規(guī)則做比較，如果不匹配，則什么都不做。
map用到了十一個參數(shù)，其中的astate,asymbol,anewstate,anewsymbol,movement,是根據(jù)相應(yīng)的\(\delta\)填入的。我們需要給每一條轉(zhuǎn)移函數(shù)映射一個相應(yīng)的map，之后，我們只要將所有的map插進循環(huán)里，就能完成程序的主體部分了。

map(state,head,cursymbol,
  astate,asymbol,anewstate,anewsymbol,movement,
  newstate,newhead,newsymbol)
=
{
# 判斷是否匹配了正確的轉(zhuǎn)移函數(shù)，如果不是則直接退出。
copy(state,t1,t1)
write(t2,astate)
Equal(t1,t2,t3,t4,t5)
if(t3)
	copy(cursymbol,t1,t2)
	write(t2,asymbol)
	Equal(t1,t2,t3,t4,t5)
	if(t3)
		# 按規(guī)則寫入新的符號、狀態(tài)并進行移動。
		write(newstate,anewstate)
		write(newsymbol,anewymbol)
		copy(head,newhead,t1)
		ifelse(movement,t1)
			inc(newhead)
		else(movement,t1)
			dec(newhead)
		endelse(t1)
	endif(t3)
endif(t3)
}

這樣，只要確定圖靈機的種類與輸入，我們就能將它翻譯為一個brainfuck程序。
在完成運行后，只要打印出數(shù)組，就能得到這臺機器運行的結(jié)果。
我們相信這個程序能翻譯任何一臺圖靈機，并且模擬它的運行，因此可以說brainfuck是圖靈完備的。

Reference

1. BF is Turing-complete-Frans Faase:https://www.iwriteiam.nl/Ha_bf_Turing.html
2. An introduction to programming in BF-Frans Faase:https://www.iwriteiam.nl/Ha_bf_intro.html
3. Bfmacro: a bf macro-interpreter-Alva L. Couch:http://www.cs.tufts.edu/~couch/bfmacro/bfmacro/
4. 《計算理論引導(dǎo)》-Michael Sipser -機械工業(yè)出版社