О теореме Успенского-Райса
Аннотация
В статье содержится подробное доказательство теоремы Успенского-Райса. Вводятся основные понятия, относящиеся к вычислимым функциям. Используется вычислительная модель «Машина с неограниченными регистрами». Изложение носит замкнутый и элементарный характер.
При поддержке: Автор благодарит С.Ф. Сопрунова за тщательное чтение начального варианта статьи и ценные замечания, существенно улучшившие изложение, Ю.В Кузнецова и М.В. Михайлюка за внимание к этой публикации и благожелательные и конструктивные комментарии.
Список литературы
1. Н.К. Верещагин, А. Шень, Вычислимые функции, М., МЦНМО, 2017.
2. С. Пилипенко, Дискретная математика 2. Конспект, 2020-2021, https://hse-tex.me/course-2/discrete-math-02-lecture-notes.pdf.
3. В.А. Успенский, Лекции о вычислимых функциях, М., Государственное издательство физико-математической литературы, 1960.
4. Ю.Ю. Кочетков, Вычислимые функции, http://kirill-andreyev.narod2.ru.
5. В.А. Успенский, А.Л. Семёнов, Теория алгоритмов: основные открытия и приложения, М., «Наука», Главная редакция физико-математической литературы, 1987.
6. А.Е. Ромащенко, https://users.mccme.ru/anromash/courses/lecture-notes-logic-computability-2013.pdf
7. В.А. Успенский, Машина Поста, Популярные лекции по математике, выпуск 54, издание второе, М., «Наука», главная редакция физико-математической литературы, 1988.
8. Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику», М., МГУ им. М.В. Ломоносова, механико-математический факультет, 2007.
Рецензия
Для цитирования:
Грюнталь А.И. О теореме Успенского-Райса. Труды НИИСИ. 2024;14(4):96-104.
For citation:
Gryuntal A. On Uspensky-Rice Theorem. SRISA Proceedings. 2024;14(4):96-104. (In Russ.)
Просмотров:
17
Послать статью по эл. почте 