Жар холодных числ и пафос бесстрастной логики
Шрифт:
116
6. П. С. Новиков. Элементы математической логики. М., 1989, с. 36.
117
7. А. Н. Нагель. Дж. Р. Ньюмен. Теорема Гёделя. М., 1970. с. 58—60.
118
8. Краткий, но достаточно ясный обзор проблематики исследований формальных систем читатель найдет в гл. I кн.: С. Клини. Математическая логика. М., 1973.
9.
119
1. Совокупность этих допущений составляет то, что обычно называют абстракцией потенциальной осуществимости. Представление об этой абстракции в явной форме было введено в логику и основания математики выдающимся советским ученым Андреем Андреевичем Марковым (род. в 1903 г.). См.: А. А. Марков. Теория алгорифмов. Труды Математического института АН СССР. т. ХШ. М.—Л.. 1954. с. 15; А. А. Марков. О логике конструктивной математики. М., 1972.
120
2. Более строго операцию подстановки можно задать следующим образом. По n-местным функциям q1..., gm и m-местной функции h строится n-местная функция f такая, что для любых x1, x2,..., Хn
f(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)).
121
3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого условного равенства . Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,-понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают.
122
4. Отметим в этой связи, что приведенное там же определение функции подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 — 138). Роль f играет функция , в качестве r берется 0, а в качестве h — проектирующая функция I12.
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. Характеристической (представляющей)
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