Теорема Райса — утверждение теории алгоритмов, согласно которому для любого нетривиального свойства вычислимых функций определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им.
Названа по имени американского математика Генри Гордона Райса, доказавшего её в 1951 году в докторской диссертации[1]. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств.
|month=
(справка); Параметры |pages=
и |page=
дублируют друг друга (справка)Для улучшения этой статьи по математике желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .