Разновидности-машин-Тьюринга.-Лекция-2.-2013-г. (Лекции Коротин)
Описание файла
Файл "Разновидности-машин-Тьюринга.-Лекция-2.-2013-г." внутри архива находится в папке "Лекции Коротин". PDF-файл из архива "Лекции Коротин", который расположен в категории "". Всё это находится в предмете "вычислительная математика" из 6 семестр, которые можно найти в файловом архиве МФТИ (ГУ). Не смотря на прямую связь этого архива с МФТИ (ГУ), его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Разновидности машинТьюрингаДоказательство существования алгоритмически неразрешимых задачДвоичная машина ТьюрингаПусть алфавит машины Т состоит из kсимволов, тогда для их кодирования машине Т*потребуется n = log2(k+1) двоичных разрядов.Анализ кортежей из n бит при движении Т*вправо будет приводить к состоянию,соответствующему считыванию символа из машиной Т.И наоборот: с каждым из k символов будемассоциировать набор из n движений влево Т* сзаписью 0 или 1, которые составят двоичныйкод символа, который записала бы машина Т. = {0,1}:( 0 -> ( 0 RX 0 -> X 0 R) 0 -> X 1 L0 0 -> 0 2 L( 1 -> X 0 RX 1 -> X 1 L0 1 -> n 0 S( 2 -> n 0 SX 2 -> X 2 L0 2 -> y 0 S( =10)=011q0 -> 1q01R0q01 -> 0q0R//(1q01 -> 1q0R//X0q0 -> 0q00R0q00 -> 0q000L //X=11=001q1 -> 1q11L1q11 -> 1q1L//X0q1 -> 1q10L0q10 -> n-S//1q10 -> 1q101R //(0q101 -> 1q0R0q000 -> 0q2L1q00 -> 1q001L //)0q001 -> 1q1L0q2 -> 0q20L0q20 -> y-S1q20 -> n-S1q2 -> 1q21L1q21 -> 1q2L////(//X = {0,1}: ( =10( 0 -> ( 0 RX 0 -> X 0 R) 0 -> X 1 L0 0 -> 0 2 L( 1 -> X 0 RX 1 -> X 1 L0 1 -> n 0 S( 2 -> n 0 SX 2 -> X 2 L0 2 -> y 0 S)=01X=111q0 -> 1q3R0q3 -> 0q0R//(1q3 -> 1q0R//X0q0 -> 0q4R0q4 -> 0q5L//0q5 -> 0q2L1q4 -> 1q6L//)0q6 -> 1q1LQ = {q0 … q11}=001q11q70q10q81q80q9->->->->->->1q7L1q1L//X1q8Ln-S //1q9R//(1q0R0q2 -> 0q10L0q10 -> y-S1q10 -> n-S1q2 -> 1q11L1q11 -> 1q2L////(//XМашина Тьюринга с лентой,бесконечной в одном направлении.………Функция вычислимая по Тьюрингуf– функция вычислимая по Тьюрингу,если её значения могут бытьвычислены некоторой машинойТьюринга, на ленте которойпервоначально не записано ничего,кроме представления x в единичномкоде, а f(x) – это то, что на лентебудет записано в единичном коде,когда машина остановится.Универсальная Машина ТьюрингаЕсли машина Т: sx Sf(x)SSf(x)x…то существует машина U: DT,sx Sf(x)DTstqtsSx f(x)…Описание Символ Состоя Рабочая лентамашиныТние ТТПроблема остановаT:1q01q1R0q01q1RDT1 0…q01q1 1q0L0q1 0q0SDT1 1q0 ли анализатор А: для T и t она выдает результат1 – в случае, если останов Т на наборе t произойдет,0 – в противном случае ?…Проблема остановаалгоритмически не разрешима.Не существует алгоритма (машиныТьюринга), позволяющего по описаниюпроизвольного алгоритма и его исходныхданных определить останавливается этоталгоритм на этих данных или работаетбесконечно.ДоказательствоПредположим обратное, тогда: А: для некоторой T(произвольной!) по данному еёописанию DT и описанию (любой!)ленты t определяет произойдетостанов или нет.DT«НЕТ»S…tq0А«Да»SШаг 1DT«НЕТ»S…DTq0А«Да»SПользуясь общностью набора данных рассмотримчастный случай, когда tDTШаг 2…DT«НЕТ»q0В«Да»SSМашина B есть композиция двух машин:1.Создает копию DT2.Машина АШаг 3…DTq0«НЕТ»BxSLRxМодифицируем код машины В добавив в составеё команд цикл (для любого возможного x)Назовем такую машину В*Свойства В*…DTq0«НЕТ»BxSLRxЕсли анализатору В* предъявлено описаниесамо применимой машины Тьюринга (т.е.машины, которая останавливается обрабатываясобственный код) он зацикливается, если несамо применимой – он останавливается.Шаг 4…DВ*q0«НЕТ»BxSLRxЯвляется ли В* само применимой машиной?Да – тогда должны попасть на ветвь, в которойреализован циклНет – должны попасть на ветвь, в которойпредусмотрен останов..