Синтаксис и семантика. Теорема Райса - Рекурсивные функции

Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е. Синтаксису программ вычисления одной или нескольких функции (и некоторым дополнительным данным) мы пытались распознать свойства самих функций, т. е. их Семантику.

В общем случае, любое свойство функций можно отождествить с некоторым классом функций (обладаюших этим свойством); тогда некоторая функция f обладает данным свойством, когда она принадлежит классу. Так, какие же свойства функций можно алгоритмически распознать по их кодам? Следующая теорема дает несколько обескураживающий ответ - никакие!

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

Для произвольного нетривиального (непустого и собственного) подкласса класса всех вычислимых функцийпроблема 'X ' неразрешима.

Доказательство (сведение к проблеме частичной остановки).

Поскольку класс разрешимых предикатов замкнут относительно операции отрицания, то проблема 'X ' разрешима тогда и только тогда, когда разрешима проблема 'X '. Поэтому, без ограничения общности можно считать, что нигде не определенная функция - обозначим ее f - принадлежит (в противном случае будем доказывать неразрешимость проблемы'X '). Пусть g - некоторая функция из (по условию, оно не пусто) и, по определению, f(x, y)=g(y), если X (x) определена, и f(x, y) не определена, в противном случае. По теореме о параметризации, найдется тотальная вычислимая функция k, такая что x, y (K(x)(y)=f(x, y) ). Тогда

Если X(x) определена, то K(x)=gи K(x) , и

Если X(x) не определена, то K(x)=f и K(x)

Таким образом, умея распознавать проблему 'X ', мы смогли бы распознать и проблему частичной остановки, что противоречит доказанному ранее.

Похожие статьи

• Теорема Клини о нормальной форме - Рекурсивные функции

  Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...

• Теорема о параметризации., Универсальные функции - Рекурсивные функции

  Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...

• Сводимость - Рекурсивные функции

  Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде...

• Неразрешимость - Рекурсивные функции

  Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...

• Теорема о параметризации - Рекурсивные функции

  Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...

• Перечислимость. - Рекурсивные функции

  В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...

• Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции

  Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...

• Рекурсивные функции

  Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...

• Теорема об универсальной функции - Рекурсивные функции

  Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...

• Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций

  Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....

• Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции

  Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...

• Теоремы о пределах, По &;nbsp;теореме&;nbsp; о связи &;nbsp;предела&;nbsp; и бесконечно малой функции: - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...

• Кодирование программ - Рекурсивные функции

  (Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...

• Сжатие графика вдоль оси ох, Отражение графика от оси ох, Отражение графика от оси оу, Построение графика функции, содержащий знак модуля, Обратная функция, теорема об обратной функции - Математика в современном мире

  Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....

• Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции

  Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...

• Непрерывность композиции, Точки разрыва - Свойства функций

  Пусть задана функция, со значениями в, и на множестве определена функция со значениями в. Тогда для любого можно вычислить, на можно определить функцию...

• ПРОИЗВОДНАЯ, ПРОИЗВОДНАЯ, ЕЕ СВОЙСТВА И ГЕОМЕТРИЧЕСКИЙ СМЫСЛ. ДИФФЕРЕНЦИАЛ. ПРОИЗВОДНАЯ ВЫСШИХ ПОРЯДКОВ - Скалярные и векторные величины, матрицы и функции

  ПРОИЗВОДНАЯ, ЕЕ СВОЙСТВА И ГЕОМЕТРИЧЕСКИЙ СМЫСЛ. ДИФФЕРЕНЦИАЛ. ПРОИЗВОДНАЯ ВЫСШИХ ПОРЯДКОВ Если отношение имеет предел при этот предел называют...

• Линейная функция - Конформное отображение

  Определение 2. Функция вида: , где - фиксированные комплексные числа, называется линейной. Определение 3. Отображение, осуществимое линейной функцией...

• Функции нескольких переменных. Предел и непрерывность. Частные производные. - Методы решения системы линейных уравнений

  Пусть u = f(x, y) - функция, определенная в области w. Рассмотрим точку М(х, у) О w и некоторое направление l, определяемое направляющими косинусами Cosa...

• Функции и ее свойства - Методы решения системы линейных уравнений

  В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...

• 7. ПРЕДЕЛ ФУНКЦИИ, ПОНЯТИЕ ФУНКЦИИ, ЧИСЛОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. ПРЕДЕЛ ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. ПРЕДЕЛ ФУНКЦИИ - Скалярные и векторные величины, матрицы и функции

  ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...

• Интегрируемость непрерывных, разрывных и монотонных функций, Основные свойства определенного интеграла - Определенные интегралы

  Теорема: Непрерывная на сегменте функция интегрируема на этом сегменте. Теорема: Если функция определена и ограничена на сегменте, и если для любого...

• Непрерывность функции - Свойства функций

  Рассмотрим функцию, определенную на промежутке Пусть. Функция называется непрерывной в точке, если Функция называется Непрерывной слева (справа) в точке,...

• Интегральная и дифференциальная функции распределения - Основы научных исследований

  Наиболее общей формой задания распределения случайных величин является Интегральная функция распределения . Она определяет вероятность того, что...

• Введение, Формулировка теоремы, Обозначения, Доказательство вспомогательных лемм - Об одной теореме теории чисел

  В данной работе доказывается методами элементарной математики "большая" или "последняя" теорема Ферма. Некоторая, излишняя в обычных случаях, подробность...

• ПРАВИЛО ЛОПИТАЛЯ - Скалярные и векторные величины, матрицы и функции

  Теорема Коши. Если при соблюдении предположений относительно функций и отношение стремится к некоторому числу при, то тогда к такому же числу будет...

• Целевая функция потребления и моделирование поведения потребителей. Понятие бюджетного множества - Бюджетное множество

  На уровне общества для описания поведения потребителей вводится целевая функция потребления. Целевая функция потребления - функция, выражающая уровень...

• ЭКСТРЕМУМ ФУНКЦИИ, ВОЗРАСТАНИЕ (УБЫВАНИЕ) ФУНКЦИЙ - Скалярные и векторные величины, матрицы и функции

  ВОЗРАСТАНИЕ (УБЫВАНИЕ) ФУНКЦИЙ Функция называется Возрастающей на некотором Промежутке , если на этом промежутке большему значению независимой переменной...

• Получение переходной функции объекта по его передаточным функциям - Моделирование математической модели теплообменника

  Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...

• Теоремы Ферма, Ролля, Лагранжа и Коши

  Введение В данном реферате рассматриваются теоремы Ферма, Ролля, Лагранжа и Коши. "Теорема - высказывание, нравственность которого установлена при помощи...

• Анализ чувствительности оптимального решения ЗЛП к вариациям коэффициентов целевой функции., Графический способ анализа чувствительности оптимального решения к вариациям C[j - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

  Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...

• Интегральная теорема Муавра-Лапласа

  Предположим, что в условиях схемы Бернулли проводится испытаний, в результате каждого из которых с вероятностью () происходит событие. Интегральная...

• Доказательство теоремы - Об одной теореме теории чисел

  Доказательство теоремы проводится отдельно для случая, когда (т. е. показатель степени в равенстве (2) - НЕЧЕТНОЕ число) и когда (т. е. показатель...

• Необходимое и достаточное условие интегрируемости, Равномерно непрерывные функции - Определенные интегралы

  Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...

• Введение, История теоремы - Великая теорема Ферма

  Она заинтересовала меня тем, что на вид очень простая и казалось бы, решить ее может каждый школьник, но найти ее решение на протяжении 358 лет пытались...

• Дискретные случайные величины. Распределение случайных величин. Примеры, Функция распределения случайной величины. Свойства. Примеры - Теория вероятности

  Опытом называется всякое осуществление определенных условий и действий, при которых наблюдается изучаемое случайное явление. Опыты можно характеризовать...

• Бесконечные пределы - Свойства функций

  Функция называется Бесконечно малой при (или, или ) если для сколь угодно малого положительного числа найдется такое положительное число (), что для всех...

• О периодических функциях - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Если функция f(x) периодична с периодом Т, то по значениям этой функции на любом отрезке длины Т можно восстановить ее значения на всей числовой прямой....

• ФУНКЦИИ, Основные понятия - Свойства функций

  Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...

• Тригонометрические функции половинного аргумента, Обратные тригонометрические функции и их свойства, Частные случаи решения тригонометрических уравнений - Действительные числа. Тригонометрические функции числового аргумента. Логарифмы. Частные случаи решения тригонометрических уравнений

  Логарифм алгебраический угол число Формулы двойного аргумента Sin 2x=2sin xЧcos x Cos 2x=cosІx-sinІx Cos 2x=1-2sinІx Cos 2x=2cosІx-1 Обратные...

Синтаксис и семантика. Теорема Райса - Рекурсивные функции

Предыдущая | Следующая