Универсальные программы - раздел Образование, АКСИОМАТИЧЕСКИАЯ ТЕОРИЯ В Этом Разделе Мы Докажем Несколько Неожиданный Результат, Состоящий В Том, Ч...
В этом разделе мы докажем несколько неожиданный результат, состоящий в том, что существуют универсальные программы, то есть программы, которые в некотором смысле реализуют все другие программы. Этот результат является одним из основных результатов теории вычислимости.
Определение 6.1. Универсальной функцией для n-местных вычислимых функцийназывается (n+1)-местная функция
.
Для примера рассмотрим функцию . Эта функция реализует все одноместные вычислимые функции . Действительно, для произвольного неотрицательного целого числа т функция совпадает с функцией . Таким образом, название функции вполне соответствует классу вычисляемых ею одноместных функций.
Ниже для простоты вместо будем писать .
Теорема 6.1.Для каждого натурального числа n универсальная функция вычислима.
Доказательство. Покажем, как можно вычислить значение функции для заданного числа m и фиксированного набора (x1, ..., xn). Неформальная процедура вычисления значения состоит в следующем: «Декодируйте число m и восстановите программу Рm. Затем имитируйте вычисление по этой программе. Если вычисление по программе заканчивается, требуемое значение содержится в регистре R1». По тезису Черча заключаем, что функция вычислима.
Определение 6.2. Любая программа Р(n), вычисляющая функцию , называется универсальной программой.
Универсальные программы полностью соответствуют своему названию. Действительно, так как универсальная программа Р(n) позволяет вычислить любую n-местную вычислимую функцию, то, по сути дела, программа Р(n) заменяет абсолютно все программы для вычисления 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. Опишите правила перехода улицы для случаев:
а) перекресток регулируемый;
б) перекресток нерегулиру
Свойства алгоритмов
Рассмотренные примеры показывают, что выполнение алгоритма разбивается на последовательность законченных действий-шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит
Уточнение понятия алгоритма
«То, что вообще может быть сказано, может быть сказано ясно, а о чем невозможно говорить - о том следует молчать».
Людвиг Витгенштейн (Эпиграф, предпосланный изложению языка про
Нумерация программ для МНР
Определение 4.1. Множество X называют счетным, если можно установить взаимно однозначное отображение
Нумерация вычислимых функций
Определение 5.1. Пусть f – n-местная функция, вычислимая по программе P с геделевым номером m = g(P). Число m будем называть индексом функции f
Алгоритмически неразрешимые проблемы
Основным стимулом, приведшим к выработке понятия алгоритма и созданию теории алгоритмов, явилась потребность доказательства неразрешимости многих проблем, возникших в различных областях математики.
S-m-n-теорема
В этом разделе мы докажем теорему, принадлежащую к числу основных результатов теории алгоритмов. Суть теоремы в следующем. Допустим, что f(х, у) - вычислимая функция. Для каждого фикс
Упражнения
8.1. Докажите, что не существует алгоритма, определяющего по тексту программы, будет ли эта программа вычислять некоторую конкретную вычислимую функцию.
8.2. 2. Покажите, что не существует
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
.
. Эта функция реализует все одноместные вычислимые функции 
. Действительно, для произвольного неотрицательного целого числа т функция 
совпадает с функцией 
. Таким образом, название функции 
.
вычислима.
для заданного числа m и фиксированного набора (x1, ..., xn). Неформальная процедура вычисления значения 
Новости и инфо для студентов