Чтение онлайн

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

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

140

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

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

141

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

142

6. В принципе возможен еще и тот случай, что шахматы есть игра, «всегда выигрышная» для черных. Но многовековый опыт игры в шахматы опровергает такую возможность.

143

7. См. М.М. Ботвинник. О кибернетической цели игры. М„ 1975.

144

8. Об эвристических машинных программах и проблемах их разработки см.вкн.:Н.Нильсон. Искусственный интеллект. Методы поиска решений. М., 1973; Дж. Слэйгл. Искусственный интеллект. Подход на основе эвристического программирования М., 1973; Е. А. Александров. Основы теории эвристических решений. Подход к изучению естественного и построению искусственного интеллекта. М. 1975.