Теорема Райса: различия между версиями

'''Теорема Райса''' — утверждение [[теория алгоритмов|теории алгоритмов]], согласно которому для любого нетривиального свойства [[вычислимая функция|вычислимых функций]] определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является [[Алгоритмически неразрешимая задача|алгоритмически неразрешимой задачей]]. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им.

Названа по имени американского математика [[Райс, Генри Гордон|Генри Гордона Райса]], доказавшего её в [[1951 год в науке|1951 году]] в докторской диссертации<ref name=rice>{{cite journal | journal = Transactions of the American Mathematical Society | first = H. G. | last = Rice |title = Classes of Recursively Enumerable Sets and Their Decision Problems | year = 1953 | month = March | volume = 74 | issue = 2 | page = 358–366 | url = http://www.ams.org/journals/tran/1953-074-02/S0002-9947-1953-0053041-6/S0002-9947-1953-0053041-6.pdf | accessdate = 2011-09-29 |pages = 358 |doi = 10.2307/1990888 }}</ref>. Изначально доказана для [[Частично рекурсивная функция|частично-рекурсивных функций]], существует аналог теоремы для [[Рекурсивное множество|рекурсивных множеств]].