Многоленточные и многоголовочные автоматы (Темы на автомат)

Многоленточныеимногоголовочные автоматы•Физическая интерпретация•Физическая интерпретация••Свойства многоленточных имногоголовочных автоматов• Проблема пустоты разрешима для многоленточныхавтоматов• Проблема пустоты неразрешима для многоголовочныхавтоматов• Проблема эквивалентности разрешима для двухленточныхавтоматов• Проблема эквивалентности неразрешима длямногоголовочных автоматовПример двухголовочногоавтомата который проверяетравенство двухпоследовательно записанныхслов в алфавите•Двухголовочный автомат моделирует работу машиныТьюринга над некоторым начальным словом если автоматдопускает единственное слово конечный протокол работымашины над ним•……состояние головка обозревает уюклетку• Слово……называется конфигурациеймашины Тьюринга• Последовательность конфигураций выписанных в томпорядке в котором они следуют в процессе работы машиныназывается протоколом••аяаяконфигурация конфигурацияаяконфигурацияаяконфигурацияПервая группа команд•Шестая группа командПеремещает одну из головок на конец всего словаАвтомат останавливается в незаключительном состоянии ислово на ленте автомата отвергаетсяВторая группа командПоочередно перемещает головки автомата которыесканируют рядом стоящие конфигурации и сравнивают их насовпадение▪ несовпадений не обнаружено ⇒ команды шестой группы▪ обнаружено несовпадение символов стоящих на одинаковыхпозициях• хотя бы один из несовпадающих символов из ⇒команды третьей группы• иначе ⇒ команды шестой группыТретья группа команд•Четвертая группа команд•Пятая группа командАвтомат активизирует головку чтобы убедиться что головкадействительно обнаружила заключительную конфигурациюконечного протокола работы машины над словом α• в программе машины есть команды которые могутпродолжить протокол ⇒ команды шестой группы• таких команд нет ⇒ автомат переходить взаключительное состояние и активизирует головкукоторая обозревает символАвтомат останавливаетсядопуская слово протокол на лентеТеоремаПроблема пустоты двухголовочных автоматов не являетсячастично разрешимойТеорема Проблема зацикливания машин Тьюринга неявляется частично разрешимойДоказательствоПредположим что проблема пустоты двухголовочныхавтоматов частично разрешимаДокажем что тогда частично разрешимой оказываетсяпроблема зацикливания машин Тьюринга что приводит кпротиворечию•ТеоремаПроблема эквивалентности двухголовочных автоматов неявляется частично разрешимойДоказательствоПредположим противноеПусть А произвольный фиксированный пустойдвухголовочный автоматТогда становится очевиден частичный алгоритмраспознавания пустоты произвольного двухголовочногоавтомата надо установить эквивалентен ли этот автоматпустому автомату АПротиворечие.