и минимизации, действительно правильно реализуют

Задача 10.1. Докажите, что машины Тьюринга

определенные в доказательстве теоремы 10.1 для примитивной рекурсии и минимизации, действительно правильно реализуют указанные операторы.
Задача 10.2. Постройте машины Тьюринга Mi0 , Mi+1, Mij, ? ij =, ? ij<, Mstart и Mend, определенные в доказательстве теоремы 10.2.
Задача 10.3.
Докажите утверждение 1, сформулированное в доказательстве теоремы 10.2, используя индукцию по построению программы ? и соответствующей м.Т. M?.
Задача 10.4. В доказательстве теоремы 10.3 рассмотрен случай, когда м.Т.

вычисляет функцию от одного аргумента f(x) . Покажите, что теорема верна и в общем случае для функций f(x1,…,xn) при любом n.
Задача 10.5.
Докажите, что отношение алгоритмической сводимости

m является рефлексивным и транзитивным.
Задача 10.6.
Доказать алгоритмическую неразрешимость следующих проблем.

По произвольной программе ? определить, является ли вычисляемая ей функция ??,y(x) постоянной константой.
По произвольной программе ? и числам a и b проверить равенство ??,y(a)=b.
По произвольной программе ? определить, является ли множество значений вычисляемой ею функции ??,y(x) бесконечным.
По произвольной паре программ ? и ?' проверить, что для всех x имеет место неравенство ??,y(x) > ??',y(x).

Задача 10.7. Докажите, что

пересечение двух разрешимых множеств является разрешимым множеством.
объединение двух разрешимых множеств является разрешимым множеством.

Задача 10.8.
Докажите, что для двух разрешимых множеств A и B их "сумма" A+B={ x+y | x

A, y

B} также является разрешимым множеством.
Задача 10.9. Пусть A - разрешимое множество, а g(x) и h(x) являются о.р.ф. Докажите, что функция

также является общерекурсивной.

Содержание раздела