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

摘要 香農的通用模擬計算機（GPAC）是連續石灰模擬計算的優雅模型

2022-09-02 · 已發表論文 · 更新 2026/03/19 上午04:21

摘要 香農的通用模擬計算機（GPAC）是連續石灰模擬計算的優雅模型。在本文中，我們考慮GPAC可計算函數的集合G在迭代下是否為閉集，即對於任何函數f(x)是否為G的元素，是否存在函數F(x, t)是G的元素，使得對於非負整數t，F(x, t) = f(t)(x)。我們證明 G 在迭代下不是封閉的，但它的一個簡單擴展是封閉的。特別是，如果我們稍微放寬 GPAC 的定義以包含邊界值…

SFI 頁面

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

原文連結

論文資訊

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

摘要

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