|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Машина ТьюрингаМатериал из CustisWikiВерсия от 07:41, 8 декабря 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Неформально, Машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной набором одной или более лент, бесконечных в обоих направлениях. Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан только один символ из некоторого конечного алфавита , где предусмотрен символ «*» для обозначения пустой ячейки. На каждой ленте имеется головка чтения-записи, и все они подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний . Имеется выделенное стартовое состояние (например, «START») и состояние (или набор состояний) завершения (например «STOP»). Перед запуском МТ находится в состоянии «START», а все головки позиционированы на нулевые ячейки соответствующих лент. На каждом шаге все головки считывают информацию из своих текущих ячеек и посылают ее управляющему модулю МТ. В зависимости от этих символов и собственного состояния управляющий модуль производит следующие операции:
Теперь то же самое более формально. Машина Тьюринга это набор , где
Удобно считать, что алфавит содержит кроме «пробела» («*») два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются ). Под входом для МТ подразумевается набор из k слов (k-кортеж слов из ), записанных на k лентах начиная с нулевых позиций. Обычно, на входные данные записывают только на первую ленту, и под входом x подразумевают k-кортеж . {\it Результатом} работы МТ на некоем входе является также k-кортеж слов из , оставшихся на лентах. Для простоты также удобно считать, что результатом является только слово на последней ленте, а все остальное — просто мусор. Также считается, что входное слово не содержит пробелов — действительно, иначе было бы невозможно определить, где кончается входное слово (Можно конечно разрешить пробелы, но тогда придется зарезервировать еще один символ — «конец ввода»). Существуют следующие обобщения машины Тьюринга:
ПримерыЕсли что-то осталось непонятным, можно рассмотреть симулятор работы МТ на языке Python, который мы будем использовать, чтобы проиллюстрировать процесс работы машин Тьюринга. def execute_MT(MT,Tape): k=MT["k"] T=MT["program"] Tape=["*"]+Tape[:] configuration={"state":MT["start"], "position":1, "tape": Tape} history=[configuration] step=0 while 1: step=step+1 #if we reach the end of the tape --- enlarge it if configuration["position"]>=len(configuration["tape"]): configuration["tape"].append("*") #the symbol we are looking at symbol=configuration["tape"][configuration["position"]] #perform transition key=(configuration["state"],(symbol)) action=T[key] # Just cloning entire configuration: (state,head position,tape) new_tape=configuration["tape"][:] new_configuration=dict(configuration) new_configuration["tape"]=new_tape configuration=new_configuration #changing state configuration["state"]=action[0] #write new symbol symbol=action[1][0] configuration["tape"][configuration["position"]]=symbol #move head move=action[1][1] if move=="L": configuration["position"]=configuration["position"]-1 if move=="R": configuration["position"]=configuration["position"]+1 #tracking configuration history.append(configuration) #if stop state - finishing if configuration["state"]==MT["stop"] or step>1000: break return history
MT={ 'k': 1, 'start': 's1', 'stop': 'q', 'program': { #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте)) ('s1', ('1')): ('s2', (('*','R'))), ('s2', ('1')): ('s2', (('1','R'))), ('s2', ('*')): ('s3', (('*','R'))), ('s3', ('*')): ('s4', (('1','L'))), ('s3', ('1')): ('s3', (('1','R'))), ('s4', ('1')): ('s4', (('1','L'))), ('s4', ('*')): ('s5', (('*','L'))), ('s5', ('1')): ('s5', (('1','L'))), ('s5', ('*')): ('s1', (('1','R'))), ('s1', ('*')): ('q', (('*',''))) } } Обратите также внимание на альтернативное представление машины Тьюринга в виде ориентированных графа, где вершинами являются состояниями, возможные переходы между ними — ребрами, причем начало ребра помечено символом, который должен быть на ленте для активации перехода, а конец ребра помечен символом, который пишется на ленту, и командой перемещения головки («L», «R», «_» ):
Симулятор возвращает историю выполнения — последовательность конфигураций (состояние, лента, положение головки) — МТ на данном входе. Например, вот три запуска симулируемой «удваивающей» МТ на строках «1», «11», «111»:
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга» |
![]() |
|||
![]() |
![]() |