歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
這一篇我們再深入看一下上次的那個復(fù)制樣例的運(yùn)行過程败富。
圖靈復(fù)制機(jī)詳解
上次我們提到它的功能是把紙帶上連續(xù)的1向左隔一個零復(fù)制一份颖侄，比如把0000011110變?yōu)?code>01111011110。通過下面的動圖可以看到上次案例的執(zhí)行情況溯革。
它的基本思路是把右邊連續(xù)的1逐個添加到左邊骄蝇。
-
00001...111[1]0膳殷，把最右邊的1變?yōu)?,得到→ -
00001...111[0]0，向左跳過所有的1乞榨，跳過中間的0→ -
00[0]01...11100秽之，（向左跳過所有的1到達(dá)1左側(cè)的0，第一遍忽略此步）→ -
00[0]01...11100吃既，把左側(cè)這個0變?yōu)?考榨，并準(zhǔn)備掉頭向右，得到→ -
00[1]01...11100鹦倚，向右河质，跳過所有的1（第一遍只有1個1）和中間的0→ -
0010[1]...11100，向右，跳過所有的1掀鹅，到達(dá)1右側(cè)的0→ -
00101...111[0]0散休，把右側(cè)這個0變?yōu)?，并掉頭向左一位乐尊，得到→ -
00101...11[1]10戚丸，這個1變?yōu)?，與步驟1相同→ -
00101...11[0]10扔嵌，向左跳過所有的1限府，跳過中間的0，與步驟2相同→ -
00[1]01...11010痢缎，向左再跳過所有的1到達(dá)1左側(cè)的0胁勺，與步驟3相同→ -
0[0]101...11010，把左側(cè)這個0變?yōu)?独旷，并準(zhǔn)備掉頭向右署穗，與步驟4相同→ -
0[1]101...11010，向右嵌洼，跳過所有的1和中間的0案疲，與步驟5相同→ -
0110[1]...11010，向右咱台，跳過所有的1络拌，到達(dá)1右側(cè)的0，與步驟6相同→ -
01101...11[0]10回溺，把右側(cè)這個0變?yōu)?春贸，并掉頭向左一位，與步驟7相同→ -
01101...1[1]110遗遵，這個1變?yōu)?萍恕，與步驟1和8相同→ -
01101...1[0]010，....如此循環(huán)→ - .....
-
00111..110[1]...11110车要，直到中間0右側(cè)最后的1→ -
00111..110[0]...11110允粤，按步驟1和8將它變?yōu)?，現(xiàn)在中間兩個0相鄰→ -
0[0]111..11001...11110翼岁，按步驟2~4向左类垫，把左側(cè)0變?yōu)?，準(zhǔn)備掉頭向右→ -
01111..11001...11110琅坡，按步驟5向右(步驟6忽略)悉患，到達(dá)中間0右側(cè)的0→ -
01111..11[0]11...11110，按步驟7把右側(cè)這個0變?yōu)?榆俺，并掉頭向左一位→ -
01111..11[0]11...11110售躁，如果發(fā)現(xiàn)這個位置是0(就是中間0)坞淮，那么就結(jié)束→
從上面的過程中我們可以知道這個圖靈機(jī)可以把紙帶上任意多個連續(xù)的1向左隔0復(fù)制出一份來，主要包含的步驟如下圖所示：
你可以對照上一篇的圖靈規(guī)則表來理解(上圖中并沒包含第1條規(guī)則S1-0和最后一條H停機(jī)狀態(tài))：
以下幾句可能有助于幫你理解上面的圖和表格：
- S2和S4相似陪捷，S3和S5相似回窘。
- 只有第2條S1-1把0變1，但有兩條把1變0市袖，它們是第5條S3-0和第9條S5-0啡直。
- 對于當(dāng)前狀態(tài)和下一狀態(tài)一致，而且也沒有P改寫的凌盯，其實(shí)是循環(huán)付枫，不斷地向前走，一直走到連續(xù)1結(jié)束出現(xiàn)0驰怎，就會跳轉(zhuǎn)到Sx-0規(guī)則。第4二打、6县忌、8、10都屬于這類继效。
- 改寫并掉頭(第5條S3-0和第9條S5-0)或者不該寫不掉頭(第3條S2-0和第7條S4-0)症杏。
- 從第9條S5-0會轉(zhuǎn)到S1看，如果中間連續(xù)兩個0瑞信，即00厉颤，第9條處于右側(cè)0[0]，那么就會向左轉(zhuǎn)到左側(cè)[0]0凡简，即到達(dá)第一條導(dǎo)致停機(jī)H狀態(tài)逼友。
歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
每個人的智能新時代
如果您發(fā)現(xiàn)文章錯誤，請不吝留言指正秤涩；
如果您覺得有用帜乞，請點(diǎn)喜歡；
如果您覺得很有用筐眷，歡迎轉(zhuǎn)載~
END
