Computability in Context - Computation and Logic in the Real World
Computability in Context - Computation and Logic in the Real World
复制标题
上下文中的可计算性 - 现实世界中的计算和逻辑
DOI：
10.1142/9781848162778_0012
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Welch P
中科院分区：
文献类型：
--
作者：
Welch P
离散计算模型，如图灵机或寄存器机的模型，如果描述了合适的极限序数行为，则可以允许transmittance运行。本章将此类模型与高级类型递归理论的经典描述联系起来，可以追溯到克莱因。使用这样的模型作为衡量标准，人们可以分析更现代的模型，例如特定物理时空中的计算，以给出这种计算形式的复杂性的界限。简要讨论了序数的计算和集合递归。
Discrete computing models, such as that of the Turing machine or of Register machines, can be allowed to run transfinitely if suitable limit ordinal behavior is described. This chapter relates such models to classical accounts of higher type recursion theory, going back to Kleene. Using such models as a yardstick, one can analyse more modern models, such as computation in particular physical spacetimes, to give bounds on the complexity of such forms of computation. Computation on ordinals and set recursion are briefly discussed.