Сводимость - Рекурсивные функции
Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде рассуждения типа "решение этой проблемы дает решение другой (известной) проблемы" или, в случае доказательства "от противного" - "если бы эта проблема решалась (таким-то образом), то другая (известная) проблема решалась бы (таким-то образом), что невозможно (приводит к противоречию)"
Приведем примеры применения метода сведения при доказательстве неразрешимости.
Теорема (примеры неразрешимости).
Следующие предикаты (проблемы) - неразрешимы:
Предикат 'X(y) определена' ( проблема остановки: предъявить алгоритм, распознающий, сходиться липрограмма x на входе y);
Предикат ' y X(y)=0' неразрешим. (проблема распознавания 0-функции).
Предикат ' y X1(y)=X2(y)' (проблема распознавания функциональной эквивалентности программ);
Доказательство.
(Сведение к частичной проблеме остановки). Если бы функция
F1= x IF ( X(y), 1, 0)
Была вычислимой, то вычислимой была бы и функция x f1(x, x),что противоречит неразрешимости проблемы 'X(x) определена'.
(Сведение к проблеме остановки).
Пусть, от противного, функция
F2= x IF ( y X(y)=0, 1, 0)
Вычислима. Тогда функция f= x, y ( X(x), 0, ) вычислима как композиция вычислимых, x, y f(x, y)=0(u(x, y)). Потеоремео параметризации, существует вычислимая функция kтакая, что x, yK(x)(y)=f(x, y).
Тогда
Если X(x) определена, то y (f(x, y)=0)и f2(k(x))=1, и
Если X(x) не определена, то y(f(x, y) неопределена),следовательно, y (f(x, y) 0) и f2(k(x))=0.
Иначе говоря, если f2 вычислима, то разрешима проблема частичной остановки, что противоречит доказанному ранее.
(Сведение к проблеме распознавания 0-функции)
Пусть, от противного, функция
F3= x1,x2 IF( y (X1(y)=X2(y) ), 1,0)
Вычислима, а c0 - некоторый индекс 0-функции, y ( C0(y)=0). Тогдаодноместнаяфункция x с(x, c0)такжевычислима, что противоречит доказанному в предыдущем пункте.
Похожие статьи
-
Синтаксис и семантика. Теорема Райса - Рекурсивные функции
Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....
-
Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции
Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...
-
Неразрешимость - Рекурсивные функции
Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...
-
Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...
-
Теорема Клини о нормальной форме - Рекурсивные функции
Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...
-
Перечислимость. - Рекурсивные функции
В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...
-
Теорема об универсальной функции - Рекурсивные функции
Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...
-
Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции
Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...
-
Теорема о параметризации - Рекурсивные функции
Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...
-
Теорема о параметризации., Универсальные функции - Рекурсивные функции
Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...
-
Кодирование программ - Рекурсивные функции
(Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...
-
Непрерывность функции - Свойства функций
Рассмотрим функцию, определенную на промежутке Пусть. Функция называется непрерывной в точке, если Функция называется Непрерывной слева (справа) в точке,...
-
Теорема: Непрерывная на сегменте функция интегрируема на этом сегменте. Теорема: Если функция определена и ограничена на сегменте, и если для любого...
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции
Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...
-
Разработан адаптивный метод решения МКО-задачи, основанный на аппроксимации функции предпочтений ЛПР с помощью нейронных сетей, аппарата нечеткой логики,...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Односторонние пределы, Пределы на бесконечности - Свойства функций
В определении предела функции предполагалось, что произвольным образом. Если при вычислении предела функции при считать, что, то получают Односторонний...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Табличное представление цен действий и состояний задачи имеет естественные ограничения по масштабируемости задачи на большую размерность. В дискретных...
-
Пусть функция определена в промежутке Х (рис.1). Исходя из некоторого значения независимой переменной, придадим ему приращение, не выводящее его из...
-
Используется адаптивная нейро-нечеткая система вывода ANFIS, функционально эквивалентная системе нечеткого вывода Сугено. Вывод осуществляется за два...
-
Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....
-
Ответ: уравнение ax2+bx+c=0. Где а не равно нулю, называется квадратным. Чтобы его решить нужно вычислить дискриминант. D=b2 -4ac и сравнить его с нулем....
-
Тригонометрические функции комплексной переменной - Конформное отображение
Определение 8. Из формулы Эйлера для всех действительных имеем Откуда , Эти формулы можно использовать для голоморфного продолжения косинуса и синуса в...
-
Пусть u = f(x, y) - функция, определенная в области w. Рассмотрим точку М(х, у) О w и некоторое направление l, определяемое направляющими косинусами Cosa...
-
Элементарные функции - Конформное отображение
Теория конформных отображений подчинена решению двух основных задач: 1) найти образ области при заданном отображении; 2) найти конформное отображение...
-
Непрерывность композиции, Точки разрыва - Свойства функций
Пусть задана функция, со значениями в, и на множестве определена функция со значениями в. Тогда для любого можно вычислить, на можно определить функцию...
-
Современные инженерные задачи оптимизации многокритериальные. Выделяют класс задач многоцелевой или многокритериальной оптимизации (класс МКО-задач). В...
-
Бесконечные пределы - Свойства функций
Функция называется Бесконечно малой при (или, или ) если для сколь угодно малого положительного числа найдется такое положительное число (), что для всех...
-
Если функция f(x) периодична с периодом Т, то по значениям этой функции на любом отрезке длины Т можно восстановить ее значения на всей числовой прямой....
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
Бесконечный предел, Замечательные пределы - Свойства функций
Наряду с бесконечно малыми существуют и бесконечно большие величины, являющиеся обратными по отношению к бесконечно малым. Поэтому является бесконечно...
-
Понятие числовой последовательности - Свойства функций
Числовой последовательностью называется числовая функция, определенная на множестве натуральных чисел . Если функцию задать на множестве натуральных...
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Логарифм алгебраический угол число Формулы двойного аргумента Sin 2x=2sin xЧcos x Cos 2x=cosІx-sinІx Cos 2x=1-2sinІx Cos 2x=2cosІx-1 Обратные...
-
Углом в один градус называется угол равный 1/180 части развернутого угла. Развернутый угол равен 180 градусам. Прямой угол равен половине развернутого...
-
ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...
-
МАТРИЦЫ И ОПЕРАЦИИ НАД НИМИ Матрицей A называется любая прямоугольная таблица, составленная из чисел, которые называют элементами матрицы и обозначается...
-
Ответ: 2) 3) 4) Знаки значений тригонометрических функций Ответ: Sin cos tg*ctg Таблица значений Ответ: Формулы сложения Ответ1 Формулы двойного...
Сводимость - Рекурсивные функции