Observability of Turing Machines: A Refinement of the Theory of Computation
Observability of Turing Machines: A Refinement of the Theory of Computation
复制标题
图灵机的可观测性：计算理论的完善
DOI：
10.15388/informatica.2010.298
复制
发表时间：
2010
期刊：
影响因子：
2.9
通讯作者：
A. Garro
中科院分区：
文献类型：
--
作者：
Y. Sergeyev;A. Garro
图灵机是一种简单的抽象计算设备，可以用来研究可计算性的极限。本文从几个角度来考虑这些问题，强调了用来描述图灵机的数学语言的重要性和相对性。深入研究了当人类(研究者)开始用不同的数学语言(调查工具)描述图灵机(研究对象)时，机械计算与其数学描述之间的相互关系。本文结合传统的数学语言，利用“可枚举集”和“连续统”等概念，提出了一种新的计算方法，可以计算不同无穷集合的元素个数。它展示了用来描述机器的数学语言如何限制了我们观察它们的可能性。特别地，引入了可观测确定图灵机和非确定图灵机的概念，并建立了保证后者可以用前者模拟的条件。
作者感谢匿名评论者提出的有用建议。这项研究得到了俄罗斯联邦项目“俄罗斯创新科学家和教育工作者”的部分支持，合同号为02.740.11.5018。
The Turing machine is one of the simple abstract computational devices that can be used to investigate the limits of computability. In this paper, they are considered from several points of view that emphasize the importance and the relativity of mathematical languages used to describe the Turing machines. A deep investigation is performed on the interrelations between mechanical computations and their mathematical descriptions emerging when a human (the researcher) starts to describe a Turing machine (the object of the study) by different mathematical languages (the instruments of investigation). Together with traditional mathematical languages using such concepts as ‘enumerable sets’ and ‘continuum’ a new computational methodology allowing one to measure the number of elements of different infinite sets is used in this paper. It is shown how mathematical languages used to describe the machines limit our possibilities to observe them. In particular, notions of observable deterministic and non-deterministic Turing machines are introduced and conditions ensuring that the latter can be simulated by the former are established.
The authors thank the anonymous reviewers for their useful suggestions. This research was partially supported by the Russian Federal Program “Scientists and Educators in Russia of Innovations”, contract number 02.740.11.5018.