摘要 我們研究香農通用模擬計算機的受限版本，其中我們只允許機器求解線性微分方程

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

我們研究香農通用模擬計算機的受限版本，其中我們只允許機器求解線性微分方程。我們證明，如果允許這台計算機以可微的方式感知不等式，那麼它就可以精確計算初等函數，即在時間和空間複雜性下封閉的最小已知遞歸類。此外，我們表明，如果機器可以存取函數 f(x)，並且隨著 x 趨向無窮大，函數 f(x) 具有適當的增長，那麼它可以在 Grzegorczyk 層次結構的任何給定層級上計算函數。更準確地說，我們表明，如果允許求解 n - 3 個某種類型的非線性微分方程，則模型恰好包含 Grzegorczyk 層次結構的第 n 層。因此，我們聲稱，至少在複雜性層次結構的這個區域中，模擬複雜性類別、計算它們的動力系統以及經典的子遞歸函數集之間存在著密切的聯繫。 (C) 2002 年愛思唯爾科學（美國）。