Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
Ревизия тезиса Чёрча-Тьюринга и формализация понятия алгоритма
2026-07-22
В статье анализируется тезис Чёрча-Тьюринга в его сильной формулировке - «любой алгоритм может быть выполнен на машине Тьюринга» - который является либо тавтологией (определяет себя через собственное же определение), либо оказывается ложным в зависимости от принятого определения термина «алгоритм». Появление новых вариаций машин Тьюринга для расширенных моделей вычислений (с произвольным доступом к памяти, недетерминированной, вероятностной, квантовой, оракульной, обратимой) интерпретируется не как уточнение исходной модели, а как симптом её принципиальной неполноты. Предлагается новое определение алгоритма, независимое от машины Тьюринга, основанное на понятии конечной системы переписывания над конечным алфавитом с явно названным невыводимым примитивом. В рамках этого определения тезис Чёрча-Тьюринга переформулируется как проверяемая математическая гипотеза и показывается, что в своей исходной форме он верен лишь для детерминированного подкласса алгоритмов. Это не обесценивает классическую теорию - она остаётся строгой и содержательной, - но меняет её эпистемический статус: из теории вычислений вообще она превращается в теорию одного, пусть и важнейшего, частного случая.
Ссылка для цитирования:
Рябиков А. Н. 2026. Ревизия тезиса Чёрча-Тьюринга и формализация понятия алгоритма. PREPRINTS.RU. https://doi.org/10.24108/preprints-3115970
Список литературы
1. Church, A. An unsolvable problem of elementary number theory // American Journal of Mathematics. - 1936. - Vol. 58, № 2. - P. 345-363.
2. Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. - 1936. - Vol. s2-42, № 1. - P. 230-265.
3. Copeland, B. J. Hypercomputation // Minds and Machines. - 2002. - Vol. 12, № 4. - P. 461-502.
4. Gandy, R. Church's thesis and principles for mechanisms // The Kleene Symposium / Ed. by J. Barwise et al. - Amsterdam : North-Holland, 1980. - P. 123-148.
5. Rabin, M. O. Probabilistic algorithm for testing primality // Journal of Number Theory. - 1980. - Vol. 12, № 1. - P. 128-138.
6. Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Journal on Computing. - 1997. - Vol. 26, № 5. - P. 1484-1509.
7. Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proceedings of the Royal Society of London A. - 1985. - Vol. 400, № 1818. - P. 97-117.
8. Gurevich, Y. Sequential abstract-state machines capture sequential algorithms // ACM Transactions on Computational Logic. - 2000. - Vol. 1, № 1. - P. 77-111.
9. Markov, A. A. Theory of Algorithms // Trudy Matematicheskogo Instituta imeni V. A. Steklova. - 1954. - Vol. 42.
10. Rice, H. G. Classes of recursively enumerable sets and their decision problems // Transactions of the American Mathematical Society. - 1953. - Vol. 74, № 2. - P. 358-366.
11. C. A. Middelburg, On the Formalization of the Notion of an Algorithm // _arXiv preprint arXiv:2401.08366v2_ - Apr. 2024.
