Упражнения - раздел Образование, АКСИОМАТИЧЕСКИАЯ ТЕОРИЯ 3.2. Составьте Алгоритмы, Вычисляющие Функции:
А) ...
3.2. Составьте алгоритмы, вычисляющие функции:
а)
б)
в)
г)
д)*
е)*
Здесь [x / y] означает наименьшее целое число, не превосходящее действительное число x / y.
3.3. Покажите, что для каждой команды переадресации существует программа без команд переадресации, которая на всякой конфигурации МНР дает тот же результат, что и T(m, n). Это означает, что команды переадресации на самом деле избыточны в нашем определении МНР. Тем не менее, представляется естественным и удобным иметь такие команды, облегчающие построение алгоритмов.
Введем еще несколько понятий необходимых для дальнейшего изложения.
Определение 3.2. n–местным предикатом на множестве M называется отображение H, сопоставляющее каждому упорядоченному набору (a1, a2, ..., an) элементов из M одно из логических значений «истинно» или «ложно».
Пример 3.4. Функции «быть простым числом», «быть четным числом» являются одноместными предикатами на множестве целых чисел.
Пример 3.5. Свойства «иметь одинаковые остатки при делении на 3» или «быть равными» являются бинарными предикатами на множестве целых чисел.
Определение 3.3. Предикат называется разрешимым, если его характеристическая функция
вычислима.
В контексте вычислимости предикаты часто называют проблемами. Поэтому ниже мы наряду с термином «разрешимый предикат» будем использовать также «разрешимая проблема».
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Упражнения
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Вопросы к экзамену
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
называется разрешимым, если его характеристическая функция
Новости и инфо для студентов