“RNN 可以逼近任何算法”的含義（和證明）
最近我讀到循環神經網絡可以逼近任何算法。
所以我的問題是：這到底是什麼意思，你能給我一個證明這一點的參考嗎？
背景
我們首先必須從計算理論中回顧一些概念。算法是計算函數的過程。給定輸入，算法必須在有限的步數內產生正確的輸出，然後終止。說一個函數是可計算的，意味著存在一個計算它的算法。在所有函數的無限集合中，大多數是不可計算的。圖靈機是一種形式化計算概念的數學模型。存在其他等效模型，但圖靈機是標準的“參考模型”。根據Church-Turing 命題，任何算法都可以用圖靈機來實現，所有可計算的函數都可以由此計算出來。圖靈機的任何特定實例僅計算特定函數。但是，存在一類特殊的圖靈機，稱為通用圖靈機，可以模擬任何其他圖靈機的任何輸入。他們通過將要模擬的機器（及其輸入）的描述作為他們自己輸入的一部分來做到這一點。因此，通用圖靈機的任何特定實例都可以計算任何可計算函數（即可以實現任何算法）。任何具有這種能力的系統都稱為圖靈完備. 證明系統是圖靈完備的一種方法是證明它可以模擬通用圖靈機。許多系統已被證明是圖靈完備的（例如大多數編程語言、某些元胞自動機和量子力學）。
遞歸神經網絡
以下論文表明，對於任何可計算函數，都存在一個可以計算它的有限循環神經網絡 (RNN)。此外，存在圖靈完備的有限 RNN，因此可以實現任何算法。
西格爾曼和桑塔格 (1992)。關於神經網絡的計算能力
他們使用包含有限數量的循環連接單元的網絡，這些單元在每個時間點接收外部輸入。每個單元的狀態由其輸入的加權和（加上一個偏差）給出，通過非線性激活函數運行。激活函數是一個飽和線性函數，是一個sigmoid的分段線性逼近。權重和偏差是固定的，因此不會發生學習。
網絡執行從二進制輸入序列到二進制輸出序列的映射。網絡有兩個外部輸入，它們被饋送到所有單元：“數據線”和“驗證線”。數據線包含零和一的輸入序列，然後在輸入序列完成後為零。驗證行讓網絡知道輸入序列何時發生。它在輸入序列的持續時間內包含一個，然後在完成後為零。一個單元被認為是“輸出單元”。它在任意延遲時輸出零，然後是零和一的輸出序列，然後在輸出序列完成後輸出零。另一個單元被認為是“驗證單元”，它讓我們知道輸出序列何時發生。
儘管這些 RNN 將二進制輸入序列映射到二進制輸出序列，但我們可能對在各種其他數學對象（其他類型的數字、向量、圖像、圖形等）上定義的函數感興趣。但是，對於任何可計算函數，這些其他類型的對象可以被編碼為二進制序列（例如，請參閱此處了解使用自然數對其他對象進行編碼的描述，而自然數又可以用二進製表示）。
結果
他們表明，對於每個可計算函數，都存在一個可以計算它的有限 RNN（上述形式）。他們通過展示可以使用 RNN 顯式模擬具有兩個堆棧的下推自動機來做到這一點。這是另一個在計算上等同於圖靈機的模型。任何可計算函數都可以由圖靈機計算。任何圖靈機都可以通過具有兩個堆棧的下推自動機來模擬。任何具有兩個堆棧的下推自動機都可以由 RNN 模擬。因此，任何可計算的函數都可以由 RNN 計算。此外，由於某些圖靈機是通用的，因此模擬它們的 RNN 是圖靈完備的，因此可以實現任何算法。特別是，他們表明存在具有 1058 個或更少單元的圖靈完備 RNN。
其他後果
模擬結果的一個有趣結果是，關於 RNN 行為的某些問題是無法確定的。這意味著不存在可以為任意 RNN 回答它們的算法（儘管它們可能在特定RNN 的情況下可以回答）。例如，一個給定的單位是否曾經取值 0 的問題是不可判定的；如果可以籠統地回答這個問題，就可以解決圖靈機的停機問題，這是不可判定的。
計算能力
在上述論文中，所有網絡參數和狀態都是有理數。這很重要，因為它限制了 RNN 的能力，並使生成的網絡更加真實。原因是有理數是可計算的數字，這意味著存在一種算法可以將它們計算到任意精度。大多數實數是不可計算的，因此無法訪問——即使是最強大的圖靈機也無法表示它們，許多人懷疑它們甚至可以在物理世界中表示。當我們在數字計算機上處理“實數”時，我們正在訪問一個更小的子集（例如 64 位浮點數）。表示任意實數需要無限的信息。
該論文稱，讓網絡訪問實數將進一步提高計算能力，超越圖靈機。Siegelmann 撰寫了許多其他論文來探索這種“超級圖靈”能力。然而，重要的是要注意這些是數學模型，結果並不意味著這樣的機器實際上可以存在於物理世界中。有充分的理由認為它不能，儘管這是一個懸而未決的問題。