Как показать, что две модели вычислений эквивалентны?

21

Я ищу объяснение того, как можно доказать, что две модели вычислений эквивалентны. Я читал книги по этому вопросу, за исключением того, что доказательства эквивалентности опущены. У меня есть базовое представление о том, что означает, что две модели вычислений эквивалентны (представление автоматов: если они принимают одни и те же языки). Есть ли другие способы мышления об эквивалентности? Если бы вы могли помочь мне понять, как доказать, что модель машины Тьюринга эквивалентна лямбда-исчислению, этого было бы достаточно.

saadtaame
источник
Я полагаю, вы выбрали не те книги.
Рафаэль
@ Рафаэль Какая хорошая книга на эту тему?
saadtaame
Я хотел бы сказать «любая книга об автоматах», но очевидно, что теперь это правда. К сожалению, у меня нет подходящих книг на английском, извините.
Рафаэль
1
Книги о автоматах не хватит.
reinierpost
Какие книги вы используете?
saadtaame

Ответы:

20

Вы показываете, что любая модель может симулировать другую, которой присвоен компьютер в модели A, показывает, что в модели B есть машина, которая выполняет ту же функцию. Обратите внимание, что это моделирование не обязательно должно быть вычислимо (но обычно так и есть).

Рассмотрим, например, автоматы с двумя стеками (2-PDA). В другом вопросе моделирование в обоих направлениях обрисовано в общих чертах. Если бы вы сделали это формально, вы бы взяли общую машину Тьюринга (кортеж) и явно сконструировали, какой будет соответствующий 2-КПК, и наоборот.


Формально такая симуляция может выглядеть так. Позволять

M=(Q,ΣI,ΣO,δ,q0,QF)

быть машиной Тьюринга (с одной лентой). Потом,

AM=(Q{q1,q2},ΣI,ΣO,δ,q1,QF)

с ΣO=ΣO.{$} и δ определяется

(q1,a,hl,hr)δ(q1,ahl,hr) для всехaΣI иhr,hlΣO ,
(q1,ε,hl,hr)δ(q2,hl,hr) для всехhr,hlΣO ,
(q2,ε,hl,hr)δ(q2,ε,hlhr) для всехhr,hlΣO сhl$ ,
(q2,ε,$,hr)δ(q0,$,hr) для всехhrΣO ,
(q,ε,hl,hr)δ(q,ε,hla)(q,hr)δ(q,a,L) для всехqQ иhlΣO ,
(q,ε,$,hr)δ(q,$,a)(q,hr)δ(q,a,L) для всехqQ ,
(q,ε,hl,hr)δ(q,ahl,ε)(q,hr)δ(q,a,R) для всехqQ,hlΣO ,
(q,ε,hl,$)δ(q,hl,$) для всехqQ иhlΣO , и
(q,ε,hl,hr)δ(q,hl,a)(q,hr)δ(q,a,N) для всехqQ,hlΣO

является эквивалентом 2-КПК. Здесь мы предполагаем, что машина Тьюринга использует ΣO качестве пустого символа, оба стека начинаются с маркера $ΣO (который никогда не удаляется) и (q,a,hl,hr)δ(q,l1li,r1rj) означает, что AM потребляет вход a , переключает состояния изq кq и обновляет стеки следующим образом:

stack update
[ источник ]

Осталось показать, что AM входит в конечное состояние на xΣI тогда и только тогда, когда это делает MЭто довольно ясно по построению; формально вы должны преобразовать принимаемые прогоны на M в принятие прогонов на AM и наоборот.

Рафаэль
источник
@frabala You were right, I had the initial states the wrong way around. Fixed now, thanks!
Raphael
4

At the beginning of Communicating and Mobile Systems: the Pi-Calculus by Robin Milner, there is a introduction on automata and how they can simulate each other so that they cannot be distinguished : Bisimulation. (cf Bisimulation on wikipedia)

I don't remember well, I should re-read the chapter, but there was a trouble with simulation and bisimulation that made them not sufficient for computational equivalences.

Thus Robin Milner introduces his Pi-Calculus and exposes it for the rest of the book.

В конце концов, в его последней книге «Пространство и движение коммуникационных агентов» вы могли взглянуть на Bigraphs Робина Милнера. Они могут моделировать автоматы, сети Петри, пи-исчисление и другие вычислительные методологии.

Стефан Роллан
источник
2

Насколько я знаю, единственный (или, по крайней мере, самый распространенный) способ сделать это - сравнить языки, которые принимают машины / модели. В этом весь смысл теории автоматов: она берет нечеткое понятие проблемы или алгоритма и превращает его в конкретный математический набор (то есть язык), о котором мы можем рассуждать.

Самый простой способ сделать это, учитывая произвольную машину / функцию из одной модели, построить машину из второй модели, которая вычисляет тот же язык. Скорее всего, вы будете использовать индукцию в длине выражения, состояния в машине, правила в грамматике и т. Д.

Я не видел, чтобы это было сделано с Lambda и TM (хотя я на 99% уверен, что это возможно), но я определенно видел такие вещи для доказательства эквивалентности NFA и регулярных выражений. Сначала вы показываете NFA, который может принимать любой атом, затем, используя индукцию, вы создаете NFA, которые принимают объединение / конкатенацию / звезду-звезду любых меньших NFA.

Затем вы делаете противоположное, чтобы найти RE для любого NFA.

jmite
источник