В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g2, f4), требовалась м.Т. M1, которая переводит конфигурацию вида |x1*|x2* |y в конфигурацию |y * |x1*|x2* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x1,x2). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?

P1 = Коп# ; par# (par* (Чист, Чист,Пуст); Зам(*,∧ ) , par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп* ); par* (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* ))

P2 = Коп# ; par# (par* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп* ; par* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Копa –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );

Пуст - не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 - прибавляет 1 к аргументу: |x⇐ |x+1

Правильный ответ:

• # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: Mconst= {n | существует константа c ∈ N такая, что ФПn,y (x) = c для всех x}. Какие из следующих функций сводят Mh0 к Mconst ? f1(n) = номер программы: ' x:= 0; Пn ; y:= 0'. f2(n) = номер программы: 'Пn ; y:= x'. f3(n) = номер программы: ' x:= 0; Пn ; y:= 0; y:= y+1'.
• # Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ? [Большая Картинка]
• # Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?
• # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ? [Большая Картинка]
• # Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1, с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст ); if Больше21 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif; Зам(#, *); Выб33. Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 2, x2 = 7 и при x1 = 3, x2 = 5, соответственно?