點(diǎn)擊上方“視學(xué)算法”，選擇加"星標(biāo)"或“置頂”
重磅干貨，第一時(shí)間送達(dá)
這幾位科學(xué)家在1996年對(duì)圖靈機(jī)進(jìn)行的論證，拿到今天來(lái)看也是值得深思的。
1996年的8月19日至23日，芬蘭的瓦薩舉行了由芬蘭人工智能協(xié)會(huì)和瓦薩大學(xué)組織的芬蘭人工智能會(huì)議。
會(huì)議上發(fā)表的一篇論文證明：圖靈機(jī)就是一個(gè)循環(huán)神經(jīng)網(wǎng)絡(luò)。
沒(méi)錯(cuò)，這是在26年前！
讓我們來(lái)看一看，這篇發(fā)表于1996年的論文。
1.1 神經(jīng)網(wǎng)絡(luò)分類
神經(jīng)網(wǎng)絡(luò)可用于分類任務(wù)，判斷輸入模式是否屬于特定的類別。長(zhǎng)期以來(lái)，人們都知道單層前饋網(wǎng)絡(luò)只能用于對(duì)線性可分的模式進(jìn)行分類，即連續(xù)層越多，類的分布就越復(fù)雜。
當(dāng)在網(wǎng)絡(luò)結(jié)構(gòu)中引入反饋時(shí)，感知器輸出值被循環(huán)利用，連續(xù)層的數(shù)量原則上變?yōu)闊o(wú)限大。
算力有沒(méi)有質(zhì)的提升？答案是肯定的。
例如，可以構(gòu)造一個(gè)分類器來(lái)判斷輸入整數(shù)是否為素?cái)?shù)。
事實(shí)證明，用于此目的的網(wǎng)絡(luò)大小可以是有限的，即使輸入整數(shù)大小不受限制，可以正確分類的素?cái)?shù)數(shù)量也是無(wú)限的。
在本文中，「由相同計(jì)算元素組成的循環(huán)網(wǎng)絡(luò)結(jié)構(gòu)」可用于完成任何（算法上的）可計(jì)算功能。
根據(jù)可計(jì)算性理論的基本公理，可以使用圖靈機(jī)實(shí)現(xiàn)可計(jì)算函數(shù)，有多種方法可以實(shí)現(xiàn)圖靈機(jī)。定義程序語(yǔ)言
。該語(yǔ)言有四種基本操作：
這里，V代表任何具有正整數(shù)值的變量，j代表任何行號(hào)。
可以證明，如果一個(gè)函數(shù)是圖靈可計(jì)算的，則可以使用這種簡(jiǎn)單的語(yǔ)言對(duì)其進(jìn)行編碼（有關(guān)詳細(xì)信息，請(qǐng)參見[1]）。
2.1 遞歸神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)
本文研究的神經(jīng)網(wǎng)絡(luò)由感知器組成，它們都具有相同的結(jié)構(gòu)，感知器數(shù)q的運(yùn)算可以定義為
其中，當(dāng)前時(shí)刻的感知器輸出（用
表示）是使用n輸入
計(jì)算的。
非線性函數(shù)f現(xiàn)在可定義為
這樣函數(shù)就可以簡(jiǎn)單地「切斷」負(fù)值，感知器網(wǎng)絡(luò)中的循環(huán)意味著感知器可以以復(fù)雜的方式組合。
圖1 遞歸神經(jīng)網(wǎng)絡(luò)的整體框架，結(jié)構(gòu)自主無(wú)外部輸入，網(wǎng)絡(luò)行為完全由初始狀態(tài)決定
在圖1中，遞歸結(jié)構(gòu)顯示在一個(gè)通用框架中：現(xiàn)在
和n是感知器的數(shù)量，從感知器p到感知器q的連接由（1）中的
標(biāo)量權(quán)重表示。
即給定初始狀態(tài)，網(wǎng)絡(luò)狀態(tài)會(huì)迭代到不再發(fā)生變化，結(jié)果可以在該穩(wěn)定狀態(tài)或網(wǎng)絡(luò)的「固定點(diǎn)」下讀取。
2.2 神經(jīng)網(wǎng)絡(luò)建構(gòu)
接下來(lái)闡述該程序
如何在感知器網(wǎng)絡(luò)中實(shí)現(xiàn)。該網(wǎng)絡(luò)由以下節(jié)點(diǎn)（或感知器）組成：- 對(duì)于程序中的每個(gè)變量V，都有一個(gè)變量節(jié)點(diǎn)
。 - 對(duì)于每個(gè)程序行i，都有一個(gè)指令節(jié)點(diǎn)
。 - 對(duì)于第i行上的每個(gè)條件分支指令，另外還有兩個(gè)轉(zhuǎn)移節(jié)點(diǎn)
和
。
語(yǔ)言程序的實(shí)現(xiàn)包括感知器網(wǎng)絡(luò)的以下變化：
- 對(duì)于程序中的每個(gè)變V，使用以下鏈接擴(kuò)充網(wǎng)絡(luò)：
- 如果程序代碼的第i行沒(méi)有操作(
)，則使用以下鏈接擴(kuò)充網(wǎng)絡(luò)（假設(shè)該節(jié)點(diǎn)
存在：
- 如果第i行有增量操作(
)，則按如下方式擴(kuò)充網(wǎng)絡(luò)：
- 如果第i行有遞減操作(
)，則按如下方式擴(kuò)充網(wǎng)絡(luò)：
- 如果第i行有條件分支(
)，則按如下方式擴(kuò)充網(wǎng)絡(luò)：
2.3 等效性證明
現(xiàn)在需要證明的是，「網(wǎng)絡(luò)的內(nèi)部狀態(tài)或網(wǎng)絡(luò)節(jié)點(diǎn)的內(nèi)容」，可以用程序狀態(tài)來(lái)標(biāo)識(shí)，同時(shí)網(wǎng)絡(luò)狀態(tài)的連續(xù)性與程序流對(duì)應(yīng)。
定義網(wǎng)絡(luò)的「合法狀態(tài)」如下：- 至所有轉(zhuǎn)換節(jié)點(diǎn)
和
（如2.2中所定義）的輸出為零(
)； - 至多一個(gè)指令節(jié)點(diǎn)
有單位輸出(
)，所有其他指令節(jié)點(diǎn)有零輸出，并且 - 變量節(jié)點(diǎn)具有非負(fù)整數(shù)輸出值。
如果所有指令節(jié)點(diǎn)的輸出均為零，則狀態(tài)最終狀態(tài)。一個(gè)合法的網(wǎng)絡(luò)狀態(tài)可以直接解釋為一個(gè)程序「快照」——如果，程序計(jì)數(shù)器在第i行，相應(yīng)的變量值存儲(chǔ)在變量節(jié)點(diǎn)中。
網(wǎng)絡(luò)狀態(tài)的變化是由非零節(jié)點(diǎn)激活的。首先，關(guān)注變量節(jié)點(diǎn)，事實(shí)證明它們表現(xiàn)為積分器，節(jié)點(diǎn)的先前內(nèi)容被循環(huán)回同一節(jié)點(diǎn)。從變量節(jié)點(diǎn)到其他節(jié)點(diǎn)的唯一連接具有負(fù)權(quán)重——這就是為什么包含零的節(jié)點(diǎn)不會(huì)改變，因?yàn)榉蔷€性的原因（2）。接下來(lái)，詳細(xì)說(shuō)明指令節(jié)點(diǎn)。假設(shè)唯一的非零指令節(jié)點(diǎn)在時(shí)間k---這對(duì)應(yīng)于程序計(jì)數(shù)器在程序代碼中第i行。若程序中第i行是
，則網(wǎng)絡(luò)向前一步的行為可表示為（只顯示受影響的節(jié)點(diǎn)）事實(shí)證明，新的網(wǎng)絡(luò)狀態(tài)再次合法。與程序代碼相比，這對(duì)應(yīng)于程序計(jì)數(shù)器被轉(zhuǎn)移到第i+1行。另一方面，如果程序中的第i行是，則向前一步的行為是這樣，除了將程序計(jì)數(shù)器轉(zhuǎn)移到下一行之外，變量V的值也會(huì)遞減。如果第i行是
，網(wǎng)絡(luò)的操作將是相同的，除了變量V的值增加。第i行的條件分支操作（IF 
GOTO j）激活更復(fù)雜的操作序列：事實(shí)證明，在這些步驟之后，網(wǎng)絡(luò)狀態(tài)可以再次被解釋為另一個(gè)程序快照。變量值已更改，token已轉(zhuǎn)移到新位置，就像執(zhí)行了相應(yīng)的程序行一樣。如果token消失，網(wǎng)絡(luò)狀態(tài)不再改變——這只有在程序計(jì)數(shù)器「超出」程序代碼時(shí)才會(huì)發(fā)生，這意味著程序終止。網(wǎng)絡(luò)的運(yùn)行也類似對(duì)應(yīng)程序的運(yùn)行，證明完成。3.1 擴(kuò)展
定義額外的流線型指令很容易，這些指令可以使編程更容易，并且生成的程序更具可讀性和執(zhí)行速度。例如，
- 第i行的無(wú)條件分支（GOTO j）可以實(shí)現(xiàn)為
- 將常量c添加到第i行的變量（
）可以實(shí)現(xiàn)為 - 行i上的另一種條件分支（IF V=0 GOTO j ）可以實(shí)現(xiàn)為
- 此外，可以同時(shí)評(píng)估各種遞增/遞減指令。假設(shè)要執(zhí)行以下操作：
。只需要一個(gè)節(jié)點(diǎn)：
上述方式絕不是實(shí)現(xiàn)圖靈機(jī)的唯一途徑。這是一個(gè)簡(jiǎn)單的實(shí)現(xiàn)，在應(yīng)用程序中不一定是最佳的。3.2 矩陣制定
上述構(gòu)造也可以以矩陣的形式實(shí)現(xiàn)。
基本思想是將變量值和「程序計(jì)數(shù)器」存儲(chǔ)在進(jìn)程狀態(tài)s中，并讓狀態(tài)轉(zhuǎn)換矩陣A代表節(jié)點(diǎn)之間的鏈接。
矩陣結(jié)構(gòu)的運(yùn)算可以定義為一個(gè)離散時(shí)間的動(dòng)態(tài)過(guò)程
其中非線性向量值函數(shù)
現(xiàn)在按元素定義，如（2）中所示。狀態(tài)轉(zhuǎn)移矩陣A的內(nèi)容很容易從網(wǎng)絡(luò)公式中解碼出來(lái)——矩陣元素是節(jié)點(diǎn)之間的權(quán)重。假設(shè)要實(shí)現(xiàn)一個(gè)簡(jiǎn)單的函數(shù)y=x，也就是說(shuō)，輸入變量x的值應(yīng)該傳遞給輸出變量y。使用語(yǔ)言可以將其編碼為（讓「入口點(diǎn)」現(xiàn)在不是第一行而是第三行）：生成的感知器網(wǎng)絡(luò)如圖2所示。實(shí)線代表正連接（權(quán)重為1），虛線代表負(fù)連接（權(quán)重-1）。與圖1相比，重新繪制了網(wǎng)絡(luò)結(jié)構(gòu)，并通過(guò)在節(jié)點(diǎn)中集成延遲元件來(lái)簡(jiǎn)化網(wǎng)絡(luò)結(jié)構(gòu)。
圖2 簡(jiǎn)單程序的網(wǎng)絡(luò)實(shí)現(xiàn)矩陣A中的前兩行/列對(duì)應(yīng)于連接到代表兩個(gè)變量Y和X的節(jié)點(diǎn)的鏈接，接下來(lái)的三行代表三個(gè)程序行（1、2和3），最后兩個(gè)代表分支指令所需的附加節(jié)點(diǎn)（3'和3''）。然后是初始（迭代前）和最終（迭代后，找到固定點(diǎn)時(shí)）的狀態(tài)如果變量節(jié)點(diǎn)的值將嚴(yán)格保在0和1之間，則動(dòng)態(tài)系統(tǒng)（3）的操作將是線性的，該函數(shù)根本沒(méi)有影響。原則上，然后可以在分析中使用線性系統(tǒng)理論。例如，在圖3中，示出了狀態(tài)轉(zhuǎn)移矩陣A的特征值。即使在上面的例子中單位圓外有特征值，非線性使得迭代總是穩(wěn)定的。事實(shí)證明，迭代總是在
步驟之后收斂，其中
。
5.1 理論方面
結(jié)果表明，圖靈機(jī)可以編碼為感知器網(wǎng)絡(luò)。根據(jù)定義，所有可計(jì)算函數(shù)都是圖靈可計(jì)算的——在可計(jì)算性理論的框架內(nèi)，不存在更強(qiáng)大的計(jì)算系統(tǒng)。循環(huán)感知器網(wǎng)絡(luò)（如上所示）是圖靈機(jī)的（又一種）形式。
這種等價(jià)的好處是可計(jì)算性理論的結(jié)果很容易獲得——例如，給定一個(gè)網(wǎng)絡(luò)和一個(gè)初始狀態(tài)，就不可能判斷這個(gè)過(guò)程最終是否會(huì)停止。上述理論等價(jià)性并沒(méi)有說(shuō)明計(jì)算效率的任何信息。與傳統(tǒng)的圖靈機(jī)實(shí)現(xiàn)（實(shí)際上是今天的計(jì)算機(jī)）相比，網(wǎng)絡(luò)中發(fā)生的不同機(jī)制可以使一些功能在這個(gè)框架中更好地實(shí)現(xiàn)。 至少在某些情況下，例如，一個(gè)算法的網(wǎng)絡(luò)實(shí)現(xiàn)可以通過(guò)允許snapshot向量中的多個(gè)「程序計(jì)數(shù)器」來(lái)被并行化。網(wǎng)絡(luò)的運(yùn)行是嚴(yán)格本地的，而不是全局的。一個(gè)有趣的問(wèn)題出現(xiàn)了，例如，是否可以在網(wǎng)絡(luò)環(huán)境中更有效地攻擊NP完全問(wèn)題！與語(yǔ)言相比，網(wǎng)絡(luò)實(shí)現(xiàn)具有以下「擴(kuò)展」：變量可以是連續(xù)的，而不僅僅是整數(shù)值。實(shí)際上，呈現(xiàn)實(shí)數(shù)的（理論）能力使網(wǎng)絡(luò)實(shí)現(xiàn)比語(yǔ)言更強(qiáng)大，所有以語(yǔ)言呈現(xiàn)的數(shù)字都是有理數(shù)。
可以同時(shí)存在各種「程序計(jì)數(shù)器」，并且控制的轉(zhuǎn)移可能是「模糊的」，這意味著指令節(jié)點(diǎn)提供的程序計(jì)數(shù)器值可能是非整數(shù)。
一個(gè)較小的擴(kuò)展是可自由定義的程序入口點(diǎn)。這可能有助于簡(jiǎn)化程序——例如，變量的復(fù)制在上面的三個(gè)程序行中完成，而名義解決方案（參見[1]）需要七行和一個(gè)額外的局部變量。
與原始程序代碼相比，矩陣公式顯然是比程序代碼更「連續(xù)」的信息表示形式——可以（經(jīng)常）修改參數(shù)，而迭代結(jié)果不會(huì)突然改變。這種「冗余」也許可以在某些應(yīng)用中使用。例如，當(dāng)使用遺傳算法（GA）進(jìn)行結(jié)構(gòu)優(yōu)化時(shí)，可以使遺傳算法中使用的隨機(jī)搜索策略更加高效：在系統(tǒng)結(jié)構(gòu)發(fā)生變化后，可以搜索連續(xù)成本函數(shù)的局部最小值使用一些傳統(tǒng)技術(shù)（參見[4]）。通過(guò)示例學(xué)習(xí)有限狀態(tài)機(jī)結(jié)構(gòu)，如[5]中所述，可以知道：在這種更復(fù)雜的情況下也采用迭代增強(qiáng)網(wǎng)絡(luò)結(jié)構(gòu)的方法。不僅神經(jīng)網(wǎng)絡(luò)理論可能受益于上述結(jié)果——僅看動(dòng)態(tài)系統(tǒng)公式（3），很明顯，在可計(jì)算性理論領(lǐng)域發(fā)現(xiàn)的所有現(xiàn)象也都以簡(jiǎn)單的形式存在——尋找非線性動(dòng)態(tài)過(guò)程。例如，停機(jī)問(wèn)題的不可判定性是系統(tǒng)論領(lǐng)域的一個(gè)有趣貢獻(xiàn)：對(duì)于任何表示為圖靈機(jī)的決策過(guò)程，都存在形式（3）的動(dòng)態(tài)系統(tǒng)，它違背了這個(gè)過(guò)程——對(duì)于例如，無(wú)法構(gòu)建通用的穩(wěn)定性分析算法。5.2 相關(guān)工作
所呈現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)與遞歸來(lái)Hopfield神經(jīng)網(wǎng)絡(luò)范式之間存在一些相似之處（例如，參見[2]）。在這兩種情況下，「輸入」都被編碼為網(wǎng)絡(luò)中的初始狀態(tài)，「輸出」在迭代后從網(wǎng)絡(luò)的最終狀態(tài)中讀取。Hopfield網(wǎng)絡(luò)的固定點(diǎn)是預(yù)編程的模式模型，輸入是「噪聲」模式——該網(wǎng)絡(luò)可用于增強(qiáng)損壞的模式。中非線性函數(shù)的展望（2）使得上述「圖靈網(wǎng)絡(luò)」中可能的狀態(tài)數(shù)量是無(wú)限的。與單元輸出始終為-1或1的Hopfield網(wǎng)絡(luò)相比，可以看出，理論上，這些網(wǎng)絡(luò)結(jié)構(gòu)有很大不同。例如，雖然Hopfield網(wǎng)絡(luò)中的穩(wěn)定點(diǎn)集是有限的，但以圖靈網(wǎng)絡(luò)為代表的程序通常具有無(wú)限數(shù)量的可能結(jié)果。Hopfield網(wǎng)絡(luò)的計(jì)算能力在[6]中進(jìn)行了討論。Petri網(wǎng)是基于事件和并發(fā)系統(tǒng)建模的強(qiáng)大工具[7]。Petri網(wǎng)由位和轉(zhuǎn)移以及連接它們的弧組成。每個(gè)地方可能包含任意數(shù)量的token，token的分布稱為Petri網(wǎng)的標(biāo)記。如果轉(zhuǎn)換的所有輸入位置都被標(biāo)記占用，則轉(zhuǎn)換可能會(huì)觸發(fā)，從每個(gè)輸入位置刪除一個(gè)標(biāo)記，并向其每個(gè)輸出位置添加一個(gè)標(biāo)記。可以證明，具有附加抑制弧的擴(kuò)展Petri網(wǎng)也具有圖靈機(jī)的能力（參見[7]）。上述圖靈網(wǎng)與Petri網(wǎng)的主要區(qū)別在于Petri網(wǎng)的框架更為復(fù)雜，具有專門定制的結(jié)構(gòu)，不能用簡(jiǎn)單的一般形式（3）來(lái)表達(dá)。1 Davis, M. and Weyuker, E.: Computability, Complexity, and Languages---Fundamentals of Theoretical Computer Science. Academic Press, New York, 1983.2 Haykin, S.: Neural Networks. A Comprehensive Foundation. Macmillan College Publishing, New York, 1994.3 Hy?tyniemi, H.: Correlations---Building Blocks of Intelligence? In ?lyn ulottuvuudet ja oppihistoria (History and dimensions of intelligence), Finnish Artificial Intelligence Society, 1995, pp. 199--226.4 Hy?tyniemi, H. and Koivo, H.: Genes, Codes, and Dynamic Systems. In Proceedings of the Second Nordic Workshop on Genetic Algorithms (NWGA'96), Vaasa, Finland, August 19--23, 1996.5 Manolios, P. and Fanelli, R.: First-Order Recurrent Neural Networks and Deterministic Finite State Automata. Neural Computation 6, 1994, pp. 1155--1173.6 Orponen, P.: The Computational Power of Discrete Hopfield Nets with Hidden Units. Neural Computation 8, 1996, pp. 403--415.7 Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice--Hall, Englewood Cliffs, New Jersey, 1981.http://users.ics.aalto.fi/tho/stes/step96/hyotyniemi1/
