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

3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого условного равенства . Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,-понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают.

122

4. Отметим в этой связи, что приведенное там же определение функции подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 — 138). Роль f играет функция , в качестве r берется 0, а в качестве h — проектирующая функция I₁².

122

5. См. А. И. Мальцев. Алгоритмы и рекурсивные функции. М., 1965, с. 12 и далее.

123

6. Имеется в виду статья: L. Kalmar. An Argument against the Plausibiolitu of Church's Thesis. «Constructivity in Mathematics. Proceedings of the Colloquium held at Amsterdam». Amsteerdam, 1959, p. 72—73.

124

7. Имеется в виду работа : А. Church. An Unsolvable Problem of Elementary Number Theory. «American Journal of Mathematics», vol. LVIII, № 2, 1936.

125

8. Характеристической (представляющей) функцией арифметического предиката P (х1, ..., Хn)называется такая арифметическая функция f, что для любого набора аргументов x1, ..., Хn

f(х1, ..., Хn) = (1, если предикат P выполняется на данном наборе) или (0, если P не выполняется на данном наборе.)

Предикат называется примитивно-, обще- или частично-рекурсивным в соответствии с типом характеристической функции.

126

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. Там же читатель найдет подробное описание Тьюринговых машин. Обращаем внимание на то, что наше изложение машины Тьюринга в соответствии с традицией, принятой в современных работах, в ряде непринципиальных пунктов отличается от тьюрингова.

127

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

128

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

129

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

130

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

131

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

132

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

133

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

134

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

135

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

136

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

137

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

138

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

139

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

140