Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
5.5.5. Упражнения
1. Доказать (во всех подробностях), что рекурсивность влечет вычислимость.
2. Показать, что следующие функции являются рекурсивными, указав способ, которым они могут быть получены из основных функций:
а) «нулевая» функция: Vx N(x)-— 0;
б) функция а(х), равная нулю для всех х, кроме х = 0, и единице для х = 0; _
в) целая часть квадратного корня ?(x) = [ Ух]\
') Сюда прежде всего относится интенсивно развивающаяся в Последние годы теория сложности вычислений (см. примечание на стр. 200). — Прим. ред. 98
Часть /. Предварительные сведения из логики и алгебры
г) целая часть частного: у (*> у) = [ у ] і и остаток от деления X на у.
3. Доказать, что если R и S — рекурсивные множества, то множества /? U S, 7? Г) S и .Я также рекурсивны.
4. Доказать, что если PnQ — рекурсивные предикаты, то предикаты PvQtPAQ и ~\Р также рекурсивны.
5. Доказать, что следующие предикаты вычислимы (использовать характеристические функции):
а) X = у,
б) х<у\
в) х\у (у делится на *);
г) Prem (я) (х есть простое число). Глава VI
КОМБИНАТОРНЫЕ СИСТЕМЫ И МАШИНЫ ТЬЮРИНГА: НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
§ 6.1. КОМБИНАТОРНЫЕ СИСТЕМЫ И МАШИНЫ ТЬЮРИНГА
Мы описали два математических объекта, введенных с целью формализовать интуитивное понимание вычислимости, а именно:
машины Тьюринга;
комбинаторные системы.
Было указано, что машины Тьюринга эквивалентны рекурсивным функциям; теперь мы покажем, что они эквивалентны также и комбинаторным системам.
6.1.1. Тьюринговы вычисления и полутуэвские системы
Пусть Z— машина Тьюринга, команды которой распределяются по трем типам:
(1) <7; S1 Sk qh
(2) qi Sj П qh
(3) qi S1 Л qt.
Напомним, что Si — это палочка «|» и что положительное целое числое m изображается посредством m + 1 палочек (иначе говоря, tn — |m+1).
Если предложить машине Z представление m числа m в качестве входного задания, то она начнет вычисление с конфигурации
qxm.
Это вычисление либо приведет к определенному результату, либо не даст никакого результата. Обозначим через Pz множество целых неотрицательных чисел, для которых вычисления приводят к некоторым результатам; в дальнейшем мы будем интересоваться не самими этими результатами, а только их существованием.
Будем предполагать (мы имеем на это право в силу п. 5.1.1), что Z заключает все промежуточные результаты вычислений между двумя маркерами h.
Паре (Z. т) мы поставим в соответствие полутуэвскую систему (ST)і с аксиомой hq^inh-, продукции этой системы выберем таким образом, чтобы некоторые ее теоремы соответствовали конфигурациям машины Z, в то время как другие теоремы позволили бы нам сопоставить заключительной конфигурации теорему
hrh,
означающую: «Z применима к т, т. е. соответствующее вычисление приводит к некоторому результату». 100
Часть /. Предварительные сведения из логики и алгебры
Проведем формальное построение системы (Sr)b
(а) Каждой команде типа (1) qiSjSkqi машины Z сопоставляется следующая продукция:
PqiSlQ^PqlSkQ.
Эта продукция обеспечивает переход от конфигурации PqiSjQ к той конфигурации, которая получается из нее применением данной команды.
(б) Каждой команде типа (2) qiSjllqi сопоставляются все продукции вида
PSkqiS1Q^PqlSkSlQ
(этих продукций столько, сколько имеется разных Sk). Их задача также состоит в переходе от конфигурации PShqiSjQ к той конфи гурации, которую дает применение рассматриваемой команды.
(в) Каждой команде типа (3) qiSjJIqi ставится в соответствие продукция
PqiSjQ^PSjqiQ,
которая выполняет ту же задачу, что и продукции типов (а) и (б).
Описанные до сих пор продукции соответствуют тем ситуациям машины Z, в которых применимы ее команды. Рассмотрим теперь те ситуации, в которых Z останавливается, т. е. ситуации, выступающие только в заключительных конфигурациях. Мы собираемся заменять результаты вычислений единственным ответом hrh (существование результата). Чтобы сделать это, введем продукции другого рода, применимые только к тем теоремам системы (ST)u которые соответствуют заключительным конфигурациям. Эти продукции таковы:
(г) PqiSjQ —> PqSjQ
для всех пар (^f, Sj), не являющихся левыми частями команд машины Z; эти продукции вводят маркер q\
(Д) PqSjQ^PqQ
— продукции, стирающие все символы, отличные от h, справа от маркера q\
(е) PqhQ -> PrhQ
— продукция, вводящая маркер г слева от маркера h;
(ж) PS,rQ^PrQ
— продукции, стирающие слева от г все символы, за исключением h.
Теперь мы можем сформулировать и доказать основную теорему данного раздела. Г л. VI. Комбинаторные системы и машины Тьюринга
101
Теорема. Машина Тьюринга Z применима к m в том и только в том случае, если выражение hrh является теоремой полутуэвской системы (ST) і с аксиомой hqiinh, поставленной в соответствие машине Z посредством описанного выше построения.
Используя символ Фреге «Ь-» (его значение будет понятно из контекста), мы можем записать эту теорему (вернее., метатеоре-му) следующим образом:
f- hrh.
