Вопрос 18. Теорема об универсальной машине Т. Теорема Шеннона и Боброу-Минского.
Универсальная МТ — это такая МТ U реализующая систему команд любой другой МТ. T=< V, Q, P, I > U=< Vu, Qu, Pu, Iu > Iu=qu1P || q1?
Машина U останавливается, если останавливается машина Т, и не должна останавливается если машина Т не останавливается.
Теорема 2.4. а) существует универсальная МТ . б) любую вычислимую по Тьюрингу функцию можно реализовать на универсальной МТ.
Доказательство:
1) Рассмотрим проблему конечности алфавита. Используем специальное кодирование системы команд, кодируем алфавит V и Q. V={e, a1, … ,am} ; Q={q0, q1, …, qn} используем следующий S-код
S( aj )=a0m-j•1j ; S( qi ) = q0n-i 1i ; S(R)=R ; S(L)=L ; S(?) = ?. В связи с тем, что мы ввели кодирование, уточним начальную конфигурацию УМТ. Iu = qu1 S(P)(левая полу лента) || (правая полу лента) S(q1) S(?) , где Т=< V, Q, P, I > ; || — признак конца системы команд. I = q1 ? — начальная конфигурация МТ Т. Определим алфавит на ленте УМТ: Vu= {e, a, q, 0, 1, ||, ?, L, R, *}
2) Преобразуем до кодирования на ленте систему команд МТ Т в эквивалентную ей систему команд работающую на правой полу ленте. Граница правой и левой полу ленты ||. Т ~ Т| (на правой полу ленте) и не содержит Е.
3) Зададим эффективную процедуру функционирования УМТ.
Шаг1) для строки S( qi ) и S( aj ) текущей конфигурации, выясним имеется ли эта строка на левой полу ленте. Если эта строка найдена, то переходим к шагу 2, если нет, то к шагу 10.
Шаг2) Помечаем найденную команду путем замены ? на *.
Шаг3) Выясняем равен ли R или L первый встретившийся знак после *. Если R то переходим на шаг 4 иначе на 7. ?1 ak aj| qi| ?2 если встретилось R: ?1 ak aj| qi| ?2 если встретилось L: ?1 qi| ak aj| ?2 ;
qi aj ? qi| aj| ak
Шаг4) В m+1 ячейку правой полу ленты, начинающийся с q записываем строку длины m+1 с левой полу ленты, начинающийся с a после * и q. ?1 ak aj| aj ?2 ?1 ak aj| q … ?2
Шаг5) В n+1 ячейку на правой полу ленте начинающейся с q записываем n+1 ячейку левой с полу ленты начинающейся с q после *. ?1 ak aj| qi| ?2
Шаг6) Заменяем на левой полу ленте * на ? и переходим к шагу 1.
Шаг7) Строку длины m+1 находим непосредственно после q на правой полу ленте заменяем на m+1 знак находящийся знак непосредственно слева от q. ak записываем перед aj ?1 q … ak aj| ?2.
Шаг8) В m+1 ячейку начинающуюся со 2-го знака a после q записать m+1 знак начинающийся с a после *. ?1 q … ak aj|| ?2.
Шаг9) В n+1 ячейку начинающуюся с q на правой полу ленте записываем n+1 знак начинающийся с q после * на левой полу ленте. ?1 qi| ak aj| ?2 переходим на шаг 6.
Шаг10) Остановка машины U.
Выводы : 1) нетрудно показать, что можно построить УМТ во внешнем алфавите из 2-х знаков. V = {0, 1} ; 2) Шеннон доказал, что существует УМТ имеющая всего 2 состояния: Qu = {q0, q1 } ; 3) Боброу и Минский доказали, что не существует УМТ имеющая 2 знака и 2 состояния: Vu= { 0, 1 } Qu = { q0, q1 } } не существует. 4) Существование УМТ означает, что описание любой МТ можно интерпретировать как a) описание работы некоторого устройства. б) как программу для УМТ. Любой алгоритм можно реализовать как аппаратно так и программно.
Вопрос 19. Теорема о не разрешимости проблемы остановки для машины Т.
Постановка задачи (проблема остановки) : Необходимо построить некоторую МТ Т0 такую, чтобы для любой МТ и некоторой строки ? ? V* во внешнем алфавите T=< V, Q, P, I >, применение МТ Т0 к описанию к МТ Т и строке начальной конфигурации : Т0( Т, ? ) = {Истина — если МТ Т(?) останавливается (вычислима) и Лож — если Т(?) не останавливается (т.е. Т(?) не вычислима).
Теорема 2.5. Не существует МТ Т0 решающей проблему остановки для произвольной МТ Т.
Доказательство (от противного) :
1) Предположим, что МТ Т0 существует , это означает то, что при начальной конфигурации на ленте система команд МТ.
Т= < VT, QT, PT, IT > ; (q01PT || ? ?T0 ( q00 {И, Л } PT || ? ) ; T0 = < V0 ,Q0 ,P0 ,I0 >
кодирование системы команд МТ Т PT и строки ? осуществляем как это было сделано при доказательстве теоремы об УМТ. || — разделительный знак.
q01 — начальное состояние МТ Т0 (Т0 — остановки) ; q00 — заключительное состояние Т0
2) Построим некоторую вспомогательную машину Т0| такую, что Т0 (Т¬, ?) останавливается , если Т(?) не останавливается и Т0| ( Т, ? ) не останавливается, если Т(?) останавливается. Введём новое заключительное состояние МТ Т0| – q00| . Используем Р0 , добавив только две команды. ( q00 Л ? q00| e R ) и ( q00 И ? q00 И E )
3) Решим задачу само применимости т.е. применим МТ Т0| к самой себе.
Т0| (Т0|, Т0| ) ; I0| = q01| PT0 || PT0| I0| = q01| P || ?
Получим противоречие : Машина Т0| останавливается при ? = РТ0| если Т0| не останавливается. Т0| не останавливается если Т0’ останавливается.
4) В связи с тем, что Т0| получена из Т0 вполне контролируемыми средствами и при этом никак ни связана с конкретной системой команд PT0 можно сделать вывод , что никакая МТ Т0 решающая проблемы остановки невозможна.
