Вопрос 13. Вычислимость по Тьюрингу. Операции над МТ.
Тезис Тьюринга: Любой алгоритм может быть реализован МТ. Замечание: Тезис Т. невозможно ни доказать, ни опровергнуть, это некоторое утверждение, которое связывает мат. теорию с объектами для которых эта теория предназначена.
Формализация алгоритма в виде МТ позволяет нам заменить некоторые неточные утверждения о существовании эффективных процессов точными утверждениями о существовании МТ, и наоборот по не существованию алгоритма.
Функцией вычислимости по Т. называется отображение множества строк начальной конфигурации во множество строк ее заключительной конфигурации. Т=<V,Q,P,I> I = qi ? , где qi ? Q , а ? ? V* . Если ? — изменяемая величина, то для каждой ? можно построить последовательность конфигураций МТ, которая приводит к строке ? qi ? ? q0 ?, q0 ? Q, ? ? V*.
Бывает случай когда МТ не останавливается, тогда результат не определен.
Правильно вычислимая функция по Т: это Y=T(x), где x множество строк начальной конфигурации x={?1, ?2, …, ?n}, это множество строк может быть счетно ?i принадлежит V* ; Y множество строк заключительной конфигурации Y = {?1, ?2, …}, ?i ? V* правильно вычислимая функция по Т такая что: a) любая ? ? x , существует строка ? принадлежащая Y, что q1? ? q0 ?; ? = Т(?), б) для всех строк ? принадлежит x и существует ? ? V*, что qi ? ? … ? qk ? ? … ? qk ? — которая зациклена.
Функция вычислимая по Т задана на множестве строк принадлежащих V*, сюда же входят всевозможные функции аргументом которых являются целые и рациональные числа.
Определение — эквивалентными называются такие МТ Т1 и Т2, которые вычисляют одну и туже функцию. Т1~Т2
Теорема 2.1. Для любой МТ существует эквивалентная ей МТ такая, которая не содержит команд вида: Т| : qi aj ? qi| aj| E .
Доказательство:
а) Пусть в Р содержится команда qi aj ? qi| aj| E , то должна существовать др. команда : qi| aj| ? qi|| aj|| dk ; заменяем на qi aj ? qi|| aj dk, это соответствует последовательности применения 2-х команд. В этом случае машина эквивалентна исходной. б) Проверяем преобразование пункта а) до тех пор пока знак Е в правой части команд, но оставляем без изменения команды вида: qi aj ? q0| aj| E эти команды не изменяются в связи с тем, что возможно сокращение алфавита Q| на состояние qi| и V| будет сокращено на aj|. в) решение этой проблемы, оставить каждую команду вида qi aj ? q0| aj| E заменяем на m+1 команду, где m — мощность |V|| после удаления знаков. (1) q0 aj| ? q0| aj| L ; (m) q0| aj| ? q0|| aj| R; q0|| — новое заключительное состояние. В итоге получим МТ Т| = <V|, Q|, P|, I|> с системой команд не содержащих знак Е, которая эквивалентна исходной МТ. q0|| ~ q0.
Любой алгоритм может быть представлен в виде композиции и разветвления.
Теорема 2.1. Если y=f1(x) и f2(y) вычислимы по Т, то композиция этих функций также вычислима по Т. f2 (f1(x)).
Доказательство:
а) Пусть заданы МТ Т1=<V1, Q1, P1, I1> и Т2 = < V2, Q2, P2, I2 > для того чтобы композиция была применима необходимо, чтобы V1= V2 ; V1 ? V2 . Представим, что Q1={ q0, q11, …, q1p }; Q2 = {q20, q21, …, q2r}
Построим новую МТ следующим образом: 1) Р = Р1 ? P2; 2) q0 заменить на q21; 3) Начальное состояние МТ является I=q11 ?=I1; 4) Q=(Q1 ? Q2) \ q10
б) Докажем, что если f1 и f2 вычислимы, то вычислима и композиция. Пусть f2(f1(x)) — определено, тогда q11 ? ?T1 q10 ? ? q21? ?T2 q20 ?

Вопрос 14. Теорема о вычислимости композиции МТ.
Теорема 2.5
Если f1(x) и f2(x) вычислимы по Тьюрингу то композиция этих функций также вычислима по Тьюрингу f2(f1(x))
Доказательство:
пусти заданны МТ1 и МТ2. МТ1 вычисляет f1(x), а МТ2 – f2(y)
построим новую МТ следующим образом P={P1?P2|q01?q12}. Предварительно преобразовав МТ1 и МТ2 для работы в стандартных конфигурациях q1?q11, q0?q02, V=V1?V2, I=I1, K0=Kоб
покажем, что композиция правильно вычислимая при помощи МТ q11?(MT1)q01?=q12??(MT2)q02?

Вопрос 15. Лемма о вычислимости предиката с восстановлением.
Р(?)=b, где b?{И, Л} ; ??V* — эта МТ которая вычисляет предикат.
Лемма 2.2. Если вычислим предикат Р(?), то вычислим предикат с восстановлением ?.
Ip = q1? ?P q0b ? заключительная конфигурация
Ip| = q1? ?P’ q0b?
Доказательство:
Разобьем машину P| на 3 части : P| = P1 , P2 , P3 ; P1: q1? =>P1 ? * q0? — копирование строки начальной конфигурации на ленте, (* — разделительный знак.) ; P2: q1? =>P2 q0b — вычисление предиката, совпадает по командам с машиной P на правой полу- ленте ; P3: ? * q1b =>P3 q0b? — удаление * и перенос перед ?.

Вопрос 16. Теорема о вычислимости разветвления машин Т.
Терема 2.3. Если функция f1 и f2 и предикат P вычислимы, то разветвление f1 и f2 по Р так же вычислимы.
Доказательство. В условии задачи есть 3 МТ. Т1 вычисляет f1 ; определим множество её состояний.
T1 : Q1={ q01, q11, q21, …, qn11 }
T2 : Q2={ q02, q12, q22, …, qn22 }
Р : Q3={ q0p, q1p, q2p, …, qnpp }
а) строим МТ Tp| вычисляющую предикат с восстановлением Ip| = q1p? =>Tp’ q0pb? ; b?{И, Л}
б) Разветвление машин T1 и T2 по Тр| является композицией машин Тр| и Т3. Т3 содержит систему команд : P3 = P1 ? P2 ? { q31, И ? q11e R , q31e Л ? q12e R}
Замечание. Машина, которая получилась как разветвление имеет 2 заключительных состояния. Для объединения заключительных состояний заменим q02 на q01.

Вопрос 17. Лемма о МТ с правой полу лентой.
Лемма 2.1. Любая функция вычислимая по Т вычислима на МТ с правой полу- лентой, т.е. не заходит за границу.
Доказательство.
Применение команд вида qiaj ? qi| aj| L, где в левой части содержится знак L, не приводит к выходу за пределы левого края ленты, все записанное на ленте вместе с устройством доступа сдвигается вправо (надо опознать конец строки). Надо потребовать чтобы I=q1 ? не содержал е.
1. Строим машину Т| ~ T= <V, Q, P, I > T| = < V|, Q|, P|, I| >
V|=V ? {e|} — вводим дополнительный пустой знак, алфавит который строим, будет состоять из объединения V и пустой строки.
2. Везде в P если встретим e заменим на e| получаем P|.
3. Для всяких команд qi aj ? qi| aj| dk ? P| (dk = L) вводим новую команду qi e ? q1(i)- запускаем. Машину i, в текущую позицию оставляем знак e, а сами смещаемся в право R: q1e ?q1(i)eR; i= (0 , n) ; где n — мощность алфавита состояний исходной машины n=|Q|, q1(i) — начальное состояние q0(i) — заключительное состояние и оно = qi Ti — это композиция 2х машин Ti| и Ti||, где Ti| — выполняет поиск знака e вправо (ищем конец текущей конфигурации на ленте). Ti|| — перепись знаков вправо на одну позицию пока не встретится пустой знак (e).
Система команд Ti| : qi aj ? qi aj R (поиск e вправо) ; qi e| ? q1e| R (m+1 знаков); q1e ? q0e L (на ленту записывается e и смещается влево). После применения МТ T| на ленте имеем в правой части состояние ? q0 ake . Ti|| применяется к этой конфигурации и содержит команды. Ti|| : a) q1aj ? q1j e R запоминаем текущий знак в устройство управления, т.к. для состояния qi и aj есть m состояний. б) q1j e ? q2 aj L . Имеем в правой части состояние ? q2 e ak e . Вывод: в результате преобразований получаем эквивалентную исходной МТ. Строка исходной конфигурации не должна содержать e.