Теорема Райса

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Названа по имени американского математика Генри Гордона Райса, доказавшего её в 1951 году в докторской диссертации[1]. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств.

Примечания[править | править код]

  1. Rice, H. G. (March 1953). “Classes of Recursively Enumerable Sets and Their Decision Problems” (PDF). Transactions of the American Mathematical Society. 74 (2): 358–366. DOI:10.2307/1990888. Дата обращения 2011-09-29. Используется устаревший параметр |month= (справка); Параметры |pages= и |page= дублируют друг друга (справка)

Литература[править | править код]