On Uspensky-Rice Theorem
Abstract
This paper contains detailed proof of the Uspensky-Rice theorem. Basic definitions related to computable functions are introduced. The computing model of an unlimited register machine is used. The presentation is of thorough and elementary nature.
References
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.
Review
For citations:
Gryuntal A. On Uspensky-Rice Theorem. SRISA Proceedings. 2024;14(4):96-104. (In Russ.)
Views:
21
Email this article 