trudyniisiТруды НИИСИSRISA Proceedings2225-73493033-6422НИЦ «КУРЧАТОВСКИЙ ИНСТИТУТ» - НИИСИtrudyniisi-111Research ArticleМАТЕМАТИЧЕСКИЕ ИССЛЕДОВАНИЯMATHEMATICAL ISSUESО теореме Успенского-РайсаOn Uspensky-Rice TheoremГрюнтальА. И.GryuntalA.

Москва

Andrey Gryuntal

grntl@niisi.ras.ruНИЦ «Курчатовский институт» – НИИСИРоссия20240912202514496104Copyright © Грюнталь А.И., 20252025Грюнталь А.И.Gryuntal A.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.t-niisi.ru/jour/article/view/111

В статье содержится подробное доказательство теоремы Успенского-Райса. Вводятся основные понятия, относящиеся к вычислимым функциям. Используется вычислительная модель «Машина с неограниченными регистрами». Изложение носит замкнутый и элементарный характер.

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.

вычислимые функциипрограммамашина с неограниченными регистрамиcomputable functionsprogramunlimited register machineАвтор благодарит С.Ф. Сопрунова за тщательное чтение начального варианта статьи и ценные замечания, существенно улучшившие изложение, Ю.В Кузнецова и М.В. Михайлюка за внимание к этой публикации и благожелательные и конструктивные комментарии.ReferencesН.К. Верещагин, А. Шень, Вычислимые функции, М., МЦНМО, 2017.Н.К. Верещагин, А. Шень, Вычислимые функции, М., МЦНМО, 2017.С. Пилипенко, Дискретная математика 2. Конспект, 2020-2021, https://hse-tex.me/course-2/discrete-math-02-lecture-notes.pdf.С. Пилипенко, Дискретная математика 2. Конспект, 2020-2021, https://hse-tex.me/course-2/discrete-math-02-lecture-notes.pdf.В.А. Успенский, Лекции о вычислимых функциях, М., Государственное издательство физико-математической литературы, 1960.В.А. Успенский, Лекции о вычислимых функциях, М., Государственное издательство физико-математической литературы, 1960.Ю.Ю. Кочетков, Вычислимые функции, http://kirill-andreyev.narod2.ru.Ю.Ю. Кочетков, Вычислимые функции, http://kirill-andreyev.narod2.ru.В.А. Успенский, А.Л. Семёнов, Теория алгоритмов: основные открытия и приложения, М., «Наука», Главная редакция физико-математической литературы, 1987.В.А. Успенский, А.Л. Семёнов, Теория алгоритмов: основные открытия и приложения, М., «Наука», Главная редакция физико-математической литературы, 1987.А.Е. Ромащенко, https://users.mccme.ru/anromash/courses/lecture-notes-logic-computability-2013.pdfА.Е. Ромащенко, https://users.mccme.ru/anromash/courses/lecture-notes-logic-computability-2013.pdfВ.А. Успенский, Машина Поста, Популярные лекции по математике, выпуск 54, издание второе, М., «Наука», главная редакция физико-математической литературы, 1988.В.А. Успенский, Машина Поста, Популярные лекции по математике, выпуск 54, издание второе, М., «Наука», главная редакция физико-математической литературы, 1988.Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику», М., МГУ им. М.В. Ломоносова, механико-математический факультет, 2007.Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику», М., МГУ им. М.В. Ломоносова, механико-математический факультет, 2007.

The authors declare that there are no conflicts of interest present.