Список Литературы
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
Дальше вместо ┐(А)
будем писать (
).
1
Диофантовыми уравнениями называются
алгебраические уравнения или системы
алгебраических уравнений с рациональными
коэффициентами, решения которых
отыскиваются в целых или рациональных
числах. Например,
.
1 Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М., 1987. С.230.
1 Часто программу для машины Тьюринга организовывают в виде таблицы.
1
Частичная функция определена, вообще
говоря, не для всех значений аргумента.
В строгом смысле частичное отображение
является произвольным подмножеством
.
Частичная функция — это однозначное
частичное отображение.
1 Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1965. С.105.
1 Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1984.
2 Полностью доказательство приведено в 5-й главе книги Э. Мендельсона «Введение в математическую логику» (М., 1971).
1 С результатами взаимного моделирования вычислительных моделей можно ознакомиться в работах: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979; Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. Новосибирск, 1967.