論文: Attention is Turing Complete, Author: Perez et al.

Transformer是一種非常火的模型，特別是在chatgpt問世之后，已經顯露出一統NLP領域的趨勢。

這篇文章提供了一種嶄新的視角去理解transformer，一個單層encoder、三層decoder的小transformer竟然就能幾乎完美地模擬一臺圖靈機。某種程度上說，它擁有至少和現代計算機一樣的計算潛力。近期，另一篇腦洞大開的工作甚至用少于13層的looped transformer，就成功地實現了絕大部分基本的計算操作。

這里記錄幾個自認為有趣的insight

為什么需要位置編碼？

眾所周知，transformer采用注意力機制，能夠識別各單詞之間的相關性，但對詞序并沒有要求。也就是說，在它看來，我愛你、我你愛，這兩句話沒有區別。因此，需要對輸入的序列進行位置編碼。

本文從計算理論的角度思考了這個問題。如果將transformer看成一個自動機，那么輸入的序列就相當于待識別的語言。如果不進行位置編碼，他就無法分辨兩種僅有位置不同的語言。更進一步，還可以證明，只要兩種語言的各字母比例相同，它就已然無法分辨。

于是這就要求transformer識別的語言集合一定具有比例不變性（proportion invariance），這樣來看，它甚至無法識別正則語言，遠遠未達到我們的預期。

比例不變性證明

然而，當加入了合適的位置編碼以后，我們甚至能使transformer模擬任意一臺圖靈機。足可見，位置編碼有多重要。

如何證明圖靈完備性？

這里采用了直接模擬圖靈機的方法。對于任意一臺圖靈機，其核心是，每個格局下的操作以及操作之后的狀態轉換。因此，我們只需要模擬出他的完整狀態表，就可以重現其計算過程，也就證明了等效性。

令人驚嘆的是，decoder部分的自回歸過程很適合模擬圖靈機的每一步操作。

如果按照機器翻譯任務來理解，這里就是對于任一輸入的語言，通過encoder將之編碼，再由decoder將至翻譯成圖靈機的每一步操作。而自回歸也恰恰對應這一步步的順序操作。

于是，我們要做的事就變成了，如何設置網絡參數，讓他能夠成功翻譯。這部分技術性很強，就不在此多說了。

下面總結了整體證明框架和思路：

證明框架

思路細節

對精度的進一步探索

證明過程中需要用到一個不現實的假定：無限精度。

若考慮精度會怎么樣呢？會限制Transformer能識別語言的復雜度。

首先我們記一個語言被TM識別的操作步數，也就是時間復雜度為T(n)。那么圖靈機讀寫頭的移動距離也最多為T(n)。

因此我們編碼時最多只需要logT(n)比特（好像Tengyu Ma組有文章說只需要loglogT(n)），同時自回歸的規模也最多只需要T(n)。

其實咱們也可以從自回歸規模考慮這一問題，畢竟現實中除了精度限制也還有算力限制。

btw，文章中用的是hard attention，那是否可以用soft呢？也可以，但softmax不是有理函數，如果考慮soft，肯定就得將精度納入考慮范圍了。

編輯：黃飛

?