Wie kann man zeigen, dass zwei Rechenmodelle gleichwertig sind?

21

Ich suche nach Erklärungen, wie man beweisen kann, dass zwei Rechenmodelle gleichwertig sind. Ich habe Bücher zu diesem Thema gelesen, mit der Ausnahme, dass Äquivalenznachweise weggelassen werden. Ich habe eine grundlegende Vorstellung davon, was es bedeutet, wenn zwei Rechenmodelle gleichwertig sind (die Automatenansicht: wenn sie dieselben Sprachen akzeptieren). Gibt es andere Denkweisen zur Äquivalenz? Wenn Sie mir helfen könnten, nachzuweisen, dass das Turing-Maschinenmodell der Lambda-Rechnung entspricht, wäre das ausreichend.

Saadtaame
quelle
Ich vermute, Sie haben die falschen Bücher gewählt.
Raphael
@Raphael Was ist ein gutes Buch zu diesem Thema?
Saadtaame
Ich würde gerne "irgendein Buch über Automaten" sagen, aber anscheinend stimmt das jetzt. Leider habe ich keine passenden englischen Bücher zur Hand, sorry.
Raphael
1
Ein Buch über Automaten allein reicht nicht aus.
Reinierpost
Welche Bücher benutzt du?
Saadtaame

Antworten:

20

Sie zeigen, dass jedes Modell simulieren kann das andere kann, das eine Maschine in Modell A erhält. Zeigen Sie, dass es eine Maschine in Modell B gibt, die dieselbe Funktion berechnet. Beachten Sie, dass diese Simulation nicht berechenbar sein muss (aber normalerweise ist).

Betrachten Sie beispielsweise Pushdown-Automaten mit zwei Stapeln (2-PDA). In einer anderen Frage werden die Simulationen in beide Richtungen skizziert. Wenn Sie dies formal tun würden, würden Sie eine allgemeine Turing-Maschine (ein Tupel) nehmen und explizit konstruieren, was der entsprechende 2-PDA sein würde und umgekehrt.


Formal kann eine solche Simulation so aussehen. Lassen

M=(Q.,Σich,ΣO,δ,q0,Q.F)

sei eine Turingmaschine (mit einem Band). Dann,

EINM=(Q.{q1,q2},Σich,ΣO,δ,q1,Q.F)

mit ΣO=ΣO.{$} und δ gegeben durch

(q1,ein,hl,hr)δ(q1,einhl,hr) für alleeinΣich undhr,hlΣO ,
(q1,ε,hl,hr)δ(q2,hl,hr) für allehr,hlΣO ,
(q2,ε,hl,hr)δ(q2,ε,hlhr) für allehr,hlΣO mithl$ ,
(q2,ε,$,hr)δ(q0,$,hr) für allehrΣO ,
(q,ε,hl,hr)δ(q,ε,hla)(q,hr)δ(q,a,L) für alleqQ undhlΣO ,
(q,ε,$,hr)δ(q,$,a)(q,hr)δ(q,a,L) für alleqQ ,
(q,ε,hl,hr)δ(q,einhl,ε)(q,hr)δ(q,ein,R) für alleqQ.,hlΣO ,
(q,ε,hl,$)δ(q,hl,$) für alleqQ. undhlΣO , und
(q,ε,hl,hr)δ(q,hl,ein)(q,hr)δ(q,ein,N) für alleqQ.,hlΣO

ist ein äquivalentes 2-PDA. Hier nehmen wir an, dass die Turing Maschine verwendet ΣO als Leersymbol, beiden Stapel beginnen mit einem Marker $ΣO (die nicht entfernt wird) , und (q,ein,hl,hr)δ(q,l1lich,r1rj) bedeutet , dass EINM Eingangs verbraucht ein , schaltet Zustände ausq bisq und aktualisiert die Stapel wie folgt:

Stack-Update
[ Quelle ]

Es bleibt zu zeigen, dass EINM genau dann in einen Endzustand an xΣich übergeht, wenn M tut. Dies ist konstruktiv ganz klar; formal müssen Sie akzeptierende Läufe auf M in akzeptierende Läufe auf EINM und umgekehrt übersetzen.

Raphael
quelle
@frabala Du hattest Recht, ich hatte die Anfangszustände falsch herum. Jetzt behoben, danke!
Raphael
4

Am Anfang von Kommunikations- und Mobilsystemen: der Pi-Kalkül von Robin Milner, gibt es eine Einführung in Automaten und wie sie sich so simulieren können, dass sie nicht unterschieden werden können: Bisimulation . (vgl. Bisimulation auf Wikipedia)

Ich erinnere mich nicht gut, ich sollte das Kapitel noch einmal lesen, aber es gab ein Problem mit der Simulation und Bisimulation, das sie für rechnerische Äquivalenzen nicht ausreichte.

So stellt Robin Milner seinen Pi-Kalkül vor und macht ihn für den Rest des Buches sichtbar.

In seinem letzten Buch The Space and Motion of Communicating Agents können Sie sich schließlich Robin Milners Bigraphs ansehen. Sie können Automaten, Petrinetze, Pi-Calculus und andere Berechnungsmethoden modellieren.

Stephane Rolland
quelle
2

Soweit ich weiß, besteht der einzige (oder zumindest häufigste) Weg darin, die Sprachen zu vergleichen, die von den Maschinen / Modellen akzeptiert werden. Das ist der springende Punkt der Automatentheorie: Sie nimmt das vage Konzept eines Problems oder eines Algorithmus und verwandelt ihn in eine konkrete mathematische Menge (dh eine Sprache), über die wir nachdenken können.

Der einfachste Weg, dies zu tun, ist, bei einer beliebigen Maschine / Funktion aus einem Modell eine Maschine aus dem zweiten Modell zu konstruieren, die dieselbe Sprache berechnet. Wahrscheinlich verwenden Sie Induktion für die Länge des Ausdrucks, Zustände in der Maschine, Regeln in der Grammatik usw.

Ich habe das mit Lambda und TMs nicht gesehen (obwohl ich zu 99% sicher bin, dass es möglich ist), aber ich habe definitiv so etwas gesehen, um die Gleichwertigkeit von NFAs und regulären Ausdrücken zu beweisen. Zuerst zeigen Sie einen NFA, der jedes Atom aufnehmen kann, dann erstellen Sie mithilfe der Induktion NFAs, die die Vereinigung / Verkettung / Kleene-Stern von allen kleineren NFAs akzeptieren.

Dann machen Sie das Gegenteil, um eine RE für eine NFA zu finden.

jmite
quelle