Жар холодных числ и пафос бесстрастной логики

[133] 10. Отметим, что приведенные нами машины Тьюринга, работающие над целыми положительными числами, служат лишь иллюстрацией тьюринговой формализации вычислительного процесса

[134] 11. Об упомянутых–и других–видах автоматов можно прочесть в интересной книге М. Г. Гаазе‑Рапопорта «Автоматы и живые организмы» (М., 1961)

[135] 12. А. А. Марков. Теория алгорифмов, с. 3 (см. примечание 1)

[136] 13. С. Я. Яновская. О некоторых чертах развития математической логики и отношении ее к техническим приложениям.– В кн.: Применение логики в науке и технике. М., 1960, с. 10.

[137] 14. Диофантово уравнение – алгебраическое уравнение с целочисленными коэффициентами, для которого отыскиваются целые решения.

[138] 15. Проблемы Гильберта. М., 1969, с. 39.

[139] 16. Ф. П. Варпаховскии. А. Н. Колмогоров. О решении десятой проблемы Гильберта.– «Квант», 1970, № 7 у с. 42.

[140] 17. Ю. В. Матиясевич. Диофантовость перечислимых множеств.–Доклады АН СССР, 1970, т. !91, № 2.

[141] 18. А. А. Марков. Теория алгорифмов. См. примечание I.

[142] 19. Существуют и другие эквивалентные рассмотренным уточнения идеи алгоритма и вычислимой функции и в их числе «финитные комбинаторные процессы» Э. Поста (машина Поста). О машине Поста см. статьи В. А. Успенского в журнале «Математика в школе», 1967, № 1–4.

[143] 20. А. А. Марков. Теория алгорифмов, с. 92 (см. примечание 1). О философской основе конструктивной математики можно прочесть в кн.: В.Н. Тростников. Конструктивные процессы в математике. (Философский аспект). М., 1975.

[144] 1. Имеется в виду, что число x представлено в двоичной системе счисления и введено в память ЭВМ. В этом случае проверка условия x = 0 сводится к выяснению того, имеет ли хотя бы один элемент ячейки памяти, отведенной иод данное число, ненулевое значение, что, очевидно, технически нетрудно осуществить. Однако мы не останавливаемся здесь на устройстве ЭВМ и ее памяти, так как нас интересует логико‑математическая сторона дела. О техническом аспекте действия ЭВМ и о физической реализации процесса запоминания см., например: Л. Н. Краснухин, П. В. Нестеров. Цифровые вычислительные машины. М. 1974.

[145] 2. Если функция f частично‑рекурсивна, то при некоторых аргументах она может быть не определена, и процесс вычисления никогда не закончится. На первый взгляд рассмотрение в этом месте лишь общерекурсивных функций ограничивает общность рассуждений, однако, как мы увидим несколько ниже, это не так.