報 每日報告新聞網
聖塔非研究所

模擬計算機中的迭代、不等式和可微分

2026-03-18 · 工作論文 · 更新 2026/03/18 下午08:32

摘要 香農通用模擬計算機 (GPAC) 是連續時間模擬計算的優雅模型。在本文中，我們考慮GPAC可計算函數的集合$G$在迭代下是否是封閉的；也就是說，對於任何函數 $f(x) \in G$ 來說，是否存在一個函數 $F(x, t) \in G$ 使得對於非負整數 $t$ 來說 $F(x, t) = f ^t (x)$。我們證明 $G$ 在迭代下不是封閉的，而是它的一個簡單擴展。…

原文連結PDF 來源

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

原文連結

論文資訊

  • 類型：工作論文
  • 編號：工作論文 #934
  • 日期：2026-03-18

摘要

香農通用模擬計算機 (GPAC) 是連續時間模擬計算的優雅模型。在本文中，我們考慮GPAC可計算函數的集合$G$在迭代下是否是封閉的；也就是說，對於任何函數 $f(x) \in G$ 來說，是否存在一個函數 $F(x, t) \in G$ 使得對於非負整數 $t$ 來說 $F(x, t) = f ^t (x)$。我們證明 $G$ 在迭代下不是封閉的，而是它的一個簡單擴展。特別是，如果我們稍微放寬 GPAC 的定義以包含邊界值問題的唯一解，或者等效地如果我們允許函數 $x^k \theta(x)$ 以可微分的方式感知不等式，則生成的類別（我們稱為 $G + \theta_k$）在迭代下是封閉的。此外，$G + \theta_k$ 包含所有原始遞歸函數，並且具有附加閉包屬性，即如果 $T(x)$ 在 $G + \theta_k$ 中，則圖靈機在 $T(x)$ 時間內可計算的 $x$ 的任何函數也在 $T(x)$ 中。