Страница 51 из 52
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
3. Заметим, что ЭВМ может вычислить или, по крайней мере, пытаться вычислить значение любой частично-рекурсивной функции (заранее не всегда известно, является ли интересующая нас функция общерекурсивной). Ибо, как показал С. К. Клини, каждую частично рекурсивную функцию можно представить в виде суперпозиции двух функций, первая из которых есть результат действия мю-оператора на некоторую примитивно рекурсивную функцию, а вторая — примитивно рекурсивная функция, вообще говоря, не совпадающая с упомянутой ранее.
140
4. И которая, конечно, абсолютно надежна в своем функционировании, то есть не допускает ошибок в переработке данных. Эта идеализация составляет содержание абстракции безошибочности как одного из упрощающих предположений, связанных с идеей эффективной вычислимости и понятием алгоритма. Об этой абстракции см. кн.: Управление, информация, интеллект. Под ред. А. И. Берга и др. М., 1976;
Б. В. Бирюков. Проблема абстракции безошибочности в логике. «Вопросы философии», 1973, №11.
141
5. См, его статьи «Машина для игры в шахматы» и «Составление программ для игры в шахматы на вычислительной машине» в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963. Обе статьи на английском языке впервые были опубликованы в 1950 году.
142
6. В принципе возможен еще и тот случай, что шахматы есть игра, «всегда выигрышная» для черных. Но многовековый опыт игры в шахматы опровергает такую возможность.
143
7. См. М.М. Ботвинник. О кибернетической цели игры. М„ 1975.
144
8. Об эвристических машинных программах и проблемах их разработки см.вкн.:Н.Нильсон. Искусственный интеллект. Методы поиска решений. М., 1973; Дж. Слэйгл. Искусственный интеллект. Подход на основе эвристического программирования М., 1973; Е. А. Александров. Основы теории эвристических решений. Подход к изучению естественного и построению искусственного интеллекта. М. 1975.
145
9. Следует отметить, что другой пионер теории вычислимости (теории алгоритмов)—А.Тьюринг—также был в числе тех, кто создавал первые универсальные цифровые вычислительные машины (этим он занялся еще до второй мировой войны, а после войны участвовал в разработке первого английского «компьютера»).
146
10. Коллега фон Неймана, хорошо его знавший, Е. Вигнер, дает выразительную характеристику этого ума. «Безупречная логика была наиболее характерной чертой его мышления. Он производил впечатление идеальной логической машины... отличительной чертой его ума была замечательная память..., он... свободно говорил на пяти языках и умел читать по-латыни и по-гречески». Трагическими были его последние дни. «Когда фон Нейман понял, что он неизлечимо болен, логика заставила его прийти к выводу, что он перестанет существовать и, следовательно, мыслить. Такое заключение, весь смысл которого непостижим для человеческого рассудка, ужаснуло его. Тяжело было видеть, как ум его, по мере того, как исчезали все надежды, терпел одно поражение за другим в борьбе с судьбой, казавшейся ему хотя и неизбежной, но тем не менее совершенно неприемлемой» (Е. Вигнер. Джон фон Нейман.— В кн.: Е. Вигнер. Этюды о симметрии. М., 1971, с. 207— 208). О фон Неймане см. также статью К. Шеннона «Вклад фон Неймана в теорию автоматов» в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963.
147
11. Дж. фон Нейман. Общая и логическая теория автоматов. В кн.: А. Тьюринг. Может ли машина мыслить? М., 1960, с. 90—91 (разрядка наша.— Лет.).
148
12. См. Б. В. Бирюков. Машина и мышление (три принципа).— В кн.: Художественное и научное творчество. Л., 1972, с. 255— 257.
149
13. Некоторые интересные проблемы сложных систем рассматриваются в кн.: Управление, информация, интеллект (см. примечание 4)
150
14. Читатель может ознакомиться с этим вопросом по работе фон Неймана, цитаты из которой мы приводили выше. На русском языке имеется также перевод труда фон Неймана «Теория самовоспроизводящихся автоматов» (закончено и отредактировано А. Бёрксом.М., 1971)
151
15. Представление о них можно почерпнуть из кн.: Б. А. Трахтенброт. Алгоритмы и вычислительные автоматы. М., 1974.
151
16. М. Бунге. Интуиция и наука. М., 1967, с. 137.
152
17. Мы не говорим здесь о тех гипотетических машинах далекого будущего, возможности которых обсуждает, например, Ст. Лем в книге «Сумма технологии» (М. 1968). И для автоматов, и для разумных существ этого «четвертого эшелона» прогнозов, которым занимается польский писатель, теряют силу нынешние категории ЭВМ и человека. Тем не менее мы рекомендуем читателю познакомиться с этой книгой, учтя послесловие к ней редакторов русского перевода.