Список Литературы

1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Ван дер Варден Б. Л. Алгебра. М.:Наука, 1976.

3. Верещагин Н. К., Шень А. Начала теории множеств. М.: МЦНМО, 1999.

4. Верещагин Н. К., Шень А. Вычислимые функции. М.: МЦНМО, 1999.

5. Верещагин Н. К., Шень А. Языки и исчисления. М.: МЦНМО, 2000.

6. Глухов М. М. Математическая логика. М., 1981.

7. Курош А. Г. Лекции по общей алгебре. М.: ГИФМЛ, 1962.

8. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995.

9. Ленг С. Алгебра. М.: Мир, 1965.

10. Мальцев А. И. Алгебраические системы. М.: Наука, 1970.

11. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.

12. Марков А. А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984.

13. Новиков П. С. Элементы математической логики. М.: Наука, 1973.

14. Носов В. А. Теория алгоритмов. М., 1990.

15. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

[1] Дальше вместо ┐(А) будем писать ().

[2] Диофантовыми уравнениями называются алгебраические уравнения или системы алгебраических уравнений с рациональными коэффициентами, решения которых отыскиваются в целых или рациональных числах. Например, .

[3] Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. М., 1987. С.230.

[4] Часто программу для машины Тьюринга организовывают в виде таблицы.

[5] Частичная функция определена, вообще говоря, не для всех значений аргумента. В строгом смысле частичное отображение является произвольным подмножеством . Частичная функция — это однозначное частичное отображение.

[6] Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965. С.105.

[7] Марков А. А., Нагорный Н. М. Теория алгорифмов. М., 1984.

[8] Полностью доказательство приведено в 5-й главе книги Э. Мендельсона «Введение в математическую логику» (М., 1971).

[9] С результатами взаимного моделирования вычислительных моделей можно ознакомиться в работах: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979; Трахтенброт Б. А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. Новосибирск, 1967.

< Предыдущая