Phase Transition between Unidirectionality and Bidirectionality
Phase Transition between Unidirectionality and Bidirectionality
复制标题
DOI：
10.1007/978-3-642-27654-5_16
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
K. Tadaki
中科院分区：
文献类型：
--
作者：
K. Tadaki
弱真值表约简的概念在递归理论中起着重要的作用。在本文中，我们介绍了这一概念的阐述，其中明确指定的使用功能的可计算范围。这种阐述使我们能够以类似于计算复杂性理论的方式处理渐近行为的概念，同时停留在可计算性理论中。我们适用于阐述集出现在统计机械解释的算法信息论。我们通过揭示一个关键现象来展示阐述的力量，即，一个相变，在统计力学的解释，这不能被捕获的弱真值表还原的原始概念。
The notion of weak truth-table reducibility plays an important role in recursion theory. In this paper, we introduce an elaboration of this notion, where a computable bound on the use function is explicitly specified. This elaboration enables us to deal with the notion of asymptotic behavior in a manner like in computational complexity theory, while staying in computability theory. We apply the elaboration to sets which appear in the statistical mechanical interpretation of algorithmic information theory. We demonstrate the power of the elaboration by revealing a critical phenomenon, i.e., a phase transition, in the statistical mechanical interpretation, which cannot be captured by the original notion of weak truth-table reducibility.