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

9. В основополагающей статье А. Тьюринга (А. М. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. «Proceedings of the London Mathematical Society», Ser. 2, vol. 42, 1936) была не только изложена его «машина», но и дана попытка проанализировать вычислительный процесс вообще. Обширный фрагмент из этой статьи Тьюринга можно в русском переводе найти в кн.: М. Минскии. Вычисления и автоматы. М., 1971, с. 138—142. Там же читатель найдет подробное описание Тьюринговых машин. Обращаем внимание на то, что наше изложение машины Тьюринга в соответствии с традицией, принятой в современных работах, в ряде непринципиальных пунктов отличается от тьюрингова.

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Заметим, что ЭВМ может вычислить или, по крайней мере, пытаться вычислить значение любой частично-рекурсивной функции (заранее не всегда известно, является ли интересующая нас функция общерекурсивной). Ибо, как показал С. К. Клини, каждую частично рекурсивную функцию можно представить в виде суперпозиции двух функций, первая из которых есть результат действия мю-оператора на некоторую примитивно рекурсивную функцию, а вторая — примитивно рекурсивная функция, вообще говоря, не совпадающая с упомянутой ранее.

4. И которая, конечно, абсолютно надежна в своем функционировании, то есть не допускает ошибок в переработке данных. Эта идеализация составляет содержание абстракции безошибочности как одного из упрощающих предположений, связанных с идеей эффективной вычислимости и понятием алгоритма. Об этой абстракции см. кн.: Управление, информация, интеллект. Под ред. А. И. Берга и др. М., 1976;

Б. В. Бирюков. Проблема абстракции безошибочности в логике. «Вопросы философии», 1973, №11.

5. См, его статьи «Машина для игры в шахматы» и «Составление программ для игры в шахматы на вычислительной машине» в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963. Обе статьи на английском языке впервые были опубликованы в 1950 году.