Unconventional Computation
Unconventional Computation
复制标题
非常规计算
DOI：
10.1007/978-3-642-03745-0_11
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Welch P
中科院分区：
文献类型：
--
作者：
Welch P
(2)顺序时间记录机器：最高可达Δ^1_1-。(3)无限时间图灵机：最高可达Π^1_2-DET(Π^1_2-Σ^0_2)及以上。在这篇文章中，我们综述了一些围绕超限递归离散模型的复杂性问题。今天，我们强调与证明理论、逆数学和二阶数论的子系统的联系，如辛普森的13。因此，我们主要关注的是分析这些模型的逻辑-数学方面的问题，而不是‘实现关注’(广义地说)。
Simple models in Malament-Hogarth spacetimes, up to Δ^1_1 or HYP.(2) Ordinal Time Register Machines: up to Π^1_1-.(3) Infinite Time Turing Machines: up to Π^1_2-Det (Σ^0_2) and beyond. In this paper we survey some of the complexity issues surrounding discrete models of transfinite recursion. We emphasise today the connections with Proof Theory, Reverse Mathematics, and Subsystems of Second Order Number Theory as set forth in Simpson’s 13. Our concerns are thus mainly the logico-mathematical ones of analysing such models rather ‘implementational concerns’(to put it broadly).