рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
S-m-n-теорема

Реферат Курсовая Конспект

Выберите учебное заведение

S-m-n-теорема

S-m-n-теорема - раздел Образование, АКСИОМАТИЧЕСКИАЯ ТЕОРИЯ В Этом Разделе Мы Докажем Теорему, Принадлежащую К Числу Основных Результатов...

В этом разделе мы докажем теорему, принадлежащую к числу основных результатов теории алгоритмов. Суть теоремы в следующем. Допустим, что f(х, у) - вычислимая функция. Для каждого фиксированного значения a переменной х функция f порождает одноместную вычислимую функцию g_a(y) = f(a, у). Из вычислимости функции g_a следует существование индекса b такого, что f(a, у) = f_b(у). Оказывается индекс b можно эффективно вычислить по параметру а.

Теорема 8.1 (s-m-n-теорема, простая форма). Пусть f(х, у) -вычислимая функция. Существует всюду определенная вычислимая функция s(x), такая, что f(х, у) = f_s(_x)(у).

Доказательство. Из вычислимости функции f(х, у) следует существование МНР-программы Pr, которая, исходя из начальной конфигурации (x, y, 0, 0, ...), вычисляет значение функции f от двух аргументов х и у. Изменим программу Pr, добавив спереди команды, преобразующие начальную конфигурацию

R₁	R₂	R₃	R₄	...
y	0	0	0	...		(*)

в конфигурацию

R₁	R₂	R₃	R₄	...
a	y	0	0	...

следующим образом:

T(1, 2)

Z(1)

Новая программа Pr1, примененная к начальной конфигурации (*), вычисляет значение функции g_a(y) = f(a, у) от одного аргумента у.

Теперь рассмотрим функцию s(a) = g(Pr1), сопоставляющую произвольному неотрицательному целому числу a геделев номер программы Pr1. Функция s всюду определена и по тезису Черча вычислима. Кроме того, по построению f_s(_a)(у) = f(a, у) для каждого .

Замечание 8.1. Сформулированную теорему называют также теоремой параметризации, поскольку она позволяет по заданной вычислимой функции f(x, у) и фиксированному параметру a найти геделев номер s(a) программы, вычисляющей функцию f_s(_a)(у) = f(a, у).

Доказанная выше теорема 8.1 является частным случаем более общей теоремы.

Теорема 8.2 (s-m-n-теорема). Пусть m, n – натуральные числа, - вычислимая функция с геделевым номером a. Существует всюду определенная вычислимая функция такая, что

Доказательство сформулированного утверждения аналогично доказательству теоремы 8.1.

Замечание 8.2. Название теоремы 8.2 связано с обозначением для функций в формулировке теоремы.

Покажем теперь, как можно использовать s-m-n-теорему для доказательства неразрешимости проблем. s-m-n-теорема часто используется для сведения проблемы «» к другим проблемам.

Теорема 8.3. Проблема «» неразрешима.

Доказательство. Рассмотрим функцию

По тезису Черча функция f(x, y) вычислима. Отсюда по s-m-n-теореме вытекает существование всюду определенной вычислимой функции s(x) такой, что . По определению функции f(x, y) имеем:

Следовательно, истинность условия можно установить, определив справедливость равенства . Тем самым мы свели проблему «» к проблеме «». Поскольку первая из них неразрешима, то неразрешима и вторая.

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

Теорема 8.4. Проблема неразрешима.

Доказательство. Допустим, что проблема разрешима. Тогда разрешима и проблема , где c – индекс функции 0 . Однако, это противоречит теореме 8.3. Таким образом, проблема неразрешима.

Замечание 8.4. Из теоремы 8.4 следует, что вопрос о том, вычисляют ли две программы одну и ту же одноместную функцию, неразрешим. Важность этого результата для теоретического программирования очевидна.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

АКСИОМАТИЧЕСКИАЯ ТЕОРИЯ

Е П Емельченков В Е Емельченков...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: S-m-n-теорема

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Вопросы к экзамену
1. Дедуктивный характер математики. Предмет математической логики, ее роль в вопросах обоснования математики. 2. Булевы функции. Табличное задание булевых функций. Задание булевых функций

Образцы экзаменационных билетов
Билет № 1 1. Дедуктивный характер математики. Предмет математической логики, ее роль в вопросах обоснования математики. 2. Формальные теории (как строится формальн

АКСИОМАТИЧЕСКИЕ ТЕОРИИ
Рассматривается аксиоматический метод построения математических теорий. Обсуждаются свойства непротиворечивости и полноты аксиоматических теорий. Греки п

Понятие аксиоматической теории
На уроке геометрии. Учитель: «Для чего мы изучаем аксиомы?» Ученик: «Чтобы их не доказывать». Аксиоматический метод не является достижением

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

Интерпретации и модели аксиоматической теории
Формулируя аксиомы в примерах предыдущего пункта, нами не учитывалась природа элементов тех множеств, которые там встречаются, а также природа других первоначальных понятий этих аксиоматических тео

Свойства аксиоматических теорий
Первый вопрос, который возникает, когда рассматривается та или иная аксиоматическая теория, - это вопрос о непротиворечивости, и полноте аксиоматической теории. Непротиворечивость является

Упражнения
5.1. Докажите непротиворечивость аксиоматической теории порядка – теории с одним бинарным отношением a, удовлетворяющим аксиомам транзитивности и антисимметричности. 5.2. Докажите н

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

Упражнения
1. Докажите независимость множества аксиом {B1, B2, B3} теории эквивалентности (пример 3.2). 2. Проверьте на независимость системы аксиом а

Интуитивное понятие алгоритма
Человек ежедневно встречается с множеством задач, возникающих в различных областях деятельности общества, например: a) подготовиться к уроку по математике; b) приготовить раствор

Упражнения
1.1. Составьте алгоритм сложения столбиком двух натуральных чисел. 1.2. Опишите правила перехода улицы для случаев: а) перекресток регулируемый; б) перекресток нерегулиру

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

Уточнение понятия алгоритма
«То, что вообще может быть сказано, может быть сказано ясно, а о чем невозможно говорить - о том следует молчать». Людвиг Витгенштейн (Эпиграф, предпосланный изложению языка про

Упражнения
3.2. Составьте алгоритмы, вычисляющие функции: а) б)

Нумерация программ для МНР
Определение 4.1. Множество X называют счетным, если можно установить взаимно однозначное отображение

Нумерация вычислимых функций
Определение 5.1. Пусть f – n-местная функция, вычислимая по программе P с геделевым номером m = g(P). Число m будем называть индексом функции f

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

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

Упражнения
8.1. Докажите, что не существует алгоритма, определяющего по тексту программы, будет ли эта программа вычислять некоторую конкретную вычислимую функцию. 8.2. 2. Покажите, что не существует