Embed Size (px)
Citation preview
Turing-Vollständigkeit von Zwei-Zähler-SystemenProseminar Automatentheorie
Albert-Ludwigs-Universität Freiburg
Robin KrahlInstitut für InformatikWintersemester 2015/16
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 2 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 3 / 38
Motivation
Motivation
Systeme mit nur zwei (unendlich großen) Integer-Variablenund den Operationen Inkrementieren und Dekrementieren
Registermaschinen...
... sind Turing-vollständig!(können jede Berechnung durchführen, die man auch miteiner Turingmaschine durchführen kann)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 4 / 38
Motivation
Motivation
Systeme mit nur zwei (unendlich großen) Integer-Variablenund den Operationen Inkrementieren und Dekrementieren
Registermaschinen...
... sind Turing-vollständig!
(können jede Berechnung durchführen, die man auch miteiner Turingmaschine durchführen kann)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 4 / 38
Motivation
Motivation
Systeme mit nur zwei (unendlich großen) Integer-Variablenund den Operationen Inkrementieren und Dekrementieren
Registermaschinen...
... sind Turing-vollständig!(können jede Berechnung durchführen, die man auch miteiner Turingmaschine durchführen kann)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 4 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 5 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 6 / 38
Pushdown-Systeme I
P = (P,Γ,∆)
Zustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×P×Γ∗)
bei jedem Übergang: oberstes Zeichen vom Stack lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 7 / 38
Pushdown-Systeme I
P = (P,Γ,∆)
Zustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×P×Γ∗)bei jedem Übergang: oberstes Zeichen vom Stack lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 7 / 38
Pushdown-Systeme I
P = (P,Γ,∆)
Zustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×P×Γ∗)bei jedem Übergang: oberstes Zeichen vom Stack lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 7 / 38
Pushdown-Systeme I
P = (P,Γ,∆)
Zustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×P×Γ∗)bei jedem Übergang: oberstes Zeichen vom Stack lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 7 / 38
Pushdown-Systeme II
Beispiel Pushdown-Systeme
abcd
abcef
Zustand p Zustand q
TOP
TOP
Übergang(p,d,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 8 / 38
Pushdown-Systeme II
Beispiel Pushdown-Systeme
abcd
abcef
Zustand p Zustand q
TOP
TOP
Übergang(p,d,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 8 / 38
Pushdown-Systeme II
Beispiel Pushdown-Systeme
abcd
abcef
Zustand p Zustand q
TOP
TOP
Übergang(p,d,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 8 / 38
Pushdown-Systeme II
Beispiel Pushdown-Systeme
abcd
abcef
Zustand p Zustand q
TOP
TOP
Übergang(p,d,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 8 / 38
Pushdown-Systeme II
Beispiel Pushdown-Systeme
abcd
abcef
Zustand p Zustand q
TOP
TOP
Übergang(p,d,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 8 / 38
n-Pushdown-Systeme I
Pn = (P,Γ,∆)
nicht einer, sondern n verschiedene Stacks
Zustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×{1, ...,n}×P×Γ∗)bei jedem Übergang: oberstes Zeichen vom Stack i lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 9 / 38
n-Pushdown-Systeme I
Pn = (P,Γ,∆)
nicht einer, sondern n verschiedene StacksZustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×{1, ...,n}×P×Γ∗)
bei jedem Übergang: oberstes Zeichen vom Stack i lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 9 / 38
n-Pushdown-Systeme I
Pn = (P,Γ,∆)
nicht einer, sondern n verschiedene StacksZustände PStackalphabet ΓÜbergangsrelation ∆ ⊆ (P×Γ×{1, ...,n}×P×Γ∗)bei jedem Übergang: oberstes Zeichen vom Stack i lesen,beliebig viele Zeichen schreiben
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 9 / 38
n-Pushdown-Systeme II
Beispiel n-Pushdown-Systeme
ec
abcd
ec
abcef
Zustand p Zustand q
Stack 1 Stack 2 Stack 1 Stack 2
TOP TOP
TOP
TOP
Übergang(p,d,2,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 10 / 38
n-Pushdown-Systeme II
Beispiel n-Pushdown-Systeme
ec
abcd
ec
abcef
Zustand p Zustand q
Stack 1 Stack 2 Stack 1 Stack 2
TOP TOP
TOP
TOP
Übergang(p,d,2,q, fe)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 10 / 38
n-Pushdown-Systeme III
Konfiguration
Konfiguration c = (p,w1, ...,wn) mit p ∈ P, wi ∈ Γ∗ (1≤ i ≤ n)Status zu einem bestimmten Zeitpunkt
aktueller Zustand pInhalt wi des Stacks i
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 11 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 12 / 38
n-Zähler-Systeme I
Z = (P,∆)
entspricht n-Pushdown-System P = (P,Γ,∆)nur zwei Stacksymbole: Γ = {Z ,Z0}
Stackinhalt ZmZ0 codiert Zahl mZ0 = 0ZZ0 = 1ZZZZ0 = 3...ZZ0ZZ verboten
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 13 / 38
n-Zähler-Systeme I
Z = (P,∆)
entspricht n-Pushdown-System P = (P,Γ,∆)nur zwei Stacksymbole: Γ = {Z ,Z0}Stackinhalt ZmZ0 codiert Zahl m
Z0 = 0ZZ0 = 1ZZZZ0 = 3...ZZ0ZZ verboten
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 13 / 38
n-Zähler-Systeme II
Beispiel n-Zähler-Systeme
Z0
ZZZ
Z0
ZZZZ
Zustand p Zustand qWert 3 Wert 4
TOP
TOP
Inkrementieren
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 14 / 38
n-Zähler-Systeme II
Beispiel n-Zähler-Systeme
Z0
ZZZ
Z0
ZZZZ
Zustand p Zustand qWert 3 Wert 4
TOP
TOP
Inkrementieren
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 14 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 15 / 38
Turingmaschinen
M = (Q,Σ,Γ,δ ,q0,␣)
Zustandsmenge QAnfangszustand q0
Bandalphabet ΓEingabealphabet Σ⊂ ΓLeerzeichen ␣ ∈ Γ\ΣÜbergangsmege δ ⊆ (Q×Γ×Q×Γ×{L,R,N})
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 16 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 17 / 38
Erreichbarkeitsproblem I
Erreichbarkeitsproblem
2-Zähler-System Z = (P,∆)Konfigurationen c1,c2 von Z
Kann ich c2 erreichen, wenn ich das System mit c1 starte?
Behauptung
Das Erreichbarkeitsproblem für 2-Zähler-Systeme ist nichtentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 18 / 38
Erreichbarkeitsproblem I
Erreichbarkeitsproblem
2-Zähler-System Z = (P,∆)Konfigurationen c1,c2 von ZKann ich c2 erreichen, wenn ich das System mit c1 starte?
Behauptung
Das Erreichbarkeitsproblem für 2-Zähler-Systeme ist nichtentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 18 / 38
Erreichbarkeitsproblem I
Erreichbarkeitsproblem
2-Zähler-System Z = (P,∆)Konfigurationen c1,c2 von ZKann ich c2 erreichen, wenn ich das System mit c1 starte?
Behauptung
Das Erreichbarkeitsproblem für 2-Zähler-Systeme ist nichtentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 18 / 38
Erreichbarkeitsproblem II
Beweisansatz
Turingmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-System
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 19 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 20 / 38
Turingmaschine −→ 2-Pushdown-System I
Ausgangslage
gegeben: Turingmaschine M = (Q,Σ,Γ,δ ,q0,␣)gesucht: 2-Pushdown-System PM = (P,Γ′,∆) undKonfigurationen c1,c2
c2 soll von c1 aus genau dann erreichbar sein, wenn M hält
HinweisHalteproblem für Turingmaschinen nicht entscheidbar!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 21 / 38
Turingmaschine −→ 2-Pushdown-System I
Ausgangslage
gegeben: Turingmaschine M = (Q,Σ,Γ,δ ,q0,␣)gesucht: 2-Pushdown-System PM = (P,Γ′,∆) undKonfigurationen c1,c2c2 soll von c1 aus genau dann erreichbar sein, wenn M hält
HinweisHalteproblem für Turingmaschinen nicht entscheidbar!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 21 / 38
Turingmaschine −→ 2-Pushdown-System I
Ausgangslage
gegeben: Turingmaschine M = (Q,Σ,Γ,δ ,q0,␣)gesucht: 2-Pushdown-System PM = (P,Γ′,∆) undKonfigurationen c1,c2c2 soll von c1 aus genau dann erreichbar sein, wenn M hält
HinweisHalteproblem für Turingmaschinen nicht entscheidbar!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 21 / 38
Turingmaschine −→ 2-Pushdown-System II
Veranschaulichung
...abc
...
TM
...a
...cb
2-PDS
Stack 1 Stack 2
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 22 / 38
Turingmaschine −→ 2-Pushdown-System II
Veranschaulichung
...abc
...
TM
...a
...cb
2-PDS
Stack 1 Stack 2
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 22 / 38
Turingmaschine −→ 2-Pushdown-System II
Veranschaulichung
...abc
...
TM
...a
...cb
2-PDS
Stack 1 Stack 2
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 22 / 38
Turingmaschine −→ 2-Pushdown-System II
Veranschaulichung
...abc
...
TM
...a
...cb
2-PDS
Stack 1 Stack 2
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 22 / 38
Turingmaschine −→ 2-Pushdown-System III
Vorgehensweise
Übergänge der Turingmaschine in 2-PDS abbildenStack 1: Band links des LesekopfesStack 2: Band am Lesekopf und rechts davon
Problem: 2-PDS kann immer nur auf einem Stack arbeitenLösung: zusätzliche Zwischenzustände (q,b) ∈ (Q×Γ), diesich einen Buchstaben merkenPM = (Q∪ (Q×Γ),Γ,∆)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 23 / 38
Turingmaschine −→ 2-Pushdown-System III
Vorgehensweise
Übergänge der Turingmaschine in 2-PDS abbildenStack 1: Band links des LesekopfesStack 2: Band am Lesekopf und rechts davonProblem: 2-PDS kann immer nur auf einem Stack arbeiten
Lösung: zusätzliche Zwischenzustände (q,b) ∈ (Q×Γ), diesich einen Buchstaben merkenPM = (Q∪ (Q×Γ),Γ,∆)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 23 / 38
Turingmaschine −→ 2-Pushdown-System IV
Beispiel: Kopfbewegung nach rechts
... c a d ... ... c b d ...
TM in p TM in qÜbergang
(p,a,q,b,R)
...c
...da
...c
...d
...cb
...d
p (q,b) q
S1 S2
S1 S2
S1 S2
Übergang(p,a,2, (q,b),ε)
Übergang((q,b),c,1,q,bc)
?
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 24 / 38
Turingmaschine −→ 2-Pushdown-System IV
Beispiel: Kopfbewegung nach rechts
... c a d ... ... c b d ...
TM in p TM in qÜbergang
(p,a,q,b,R)
...c
...da
...c
...d
...cb
...d
p (q,b) q
S1 S2 S1 S2 S1 S2
Übergang(p,a,2, (q,b),ε)
Übergang((q,b),c,1,q,bc)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 24 / 38
Turingmaschine −→ 2-Pushdown-System IV
Beispiel: Kopfbewegung nach rechts
... c a d ... ... c b d ...
TM in p TM in qÜbergang
(p,a,q,b,R)
...c
...da
...c
...d
...cb
...d
p (q,b) q
S1 S2 S1 S2 S1 S2
Übergang(p,a,2, (q,b),ε)
Übergang((q,b),c,1,q,bc)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 24 / 38
Turingmaschine −→ 2-Pushdown-System III
Vorgehensweise
Übergänge der Turingmaschine in 2-PDS abbildenStack 1: Band links des LesekopfesStack 2: Band am Lesekopf und rechts davonProblem: 2-PDS kann immer nur auf einem Stack arbeitenLösung: zusätzliche Zwischenzustände (q,b) ∈ (Q×Γ), diesich einen Buchstaben merken
PM = (Q∪ (Q×Γ),Γ,∆)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 25 / 38
Turingmaschine −→ 2-Pushdown-System III
Vorgehensweise
Übergänge der Turingmaschine in 2-PDS abbildenStack 1: Band links des LesekopfesStack 2: Band am Lesekopf und rechts davonProblem: 2-PDS kann immer nur auf einem Stack arbeitenLösung: zusätzliche Zwischenzustände (q,b) ∈ (Q×Γ), diesich einen Buchstaben merkenPM = (Q∪ (Q×Γ),Γ,∆)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 25 / 38
Turingmaschine −→ 2-Pushdown-System V
Beispiel: Kopfbewegung nach rechts (Fortsetzung)
Übergang der Turingmaschine (p,a,q,b,R) ∈ δ
Zeichen an der alten Kopfposition lesen und löschen:neuer Übergang (p,a,2, (q,b),ε)
Neues Zeichen hinter der neuen Kopfposition einfügen:neuer Übergang ((q,b),c,1,q,bc)... für alle c ∈ Γ... analog für keine Kopfbewegung (N) oder Kopfbewegungnach links (L)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 26 / 38
Turingmaschine −→ 2-Pushdown-System V
Beispiel: Kopfbewegung nach rechts (Fortsetzung)
Übergang der Turingmaschine (p,a,q,b,R) ∈ δ
Zeichen an der alten Kopfposition lesen und löschen:neuer Übergang (p,a,2, (q,b),ε)Neues Zeichen hinter der neuen Kopfposition einfügen:neuer Übergang ((q,b),c,1,q,bc)
... für alle c ∈ Γ
... analog für keine Kopfbewegung (N) oder Kopfbewegungnach links (L)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 26 / 38
Turingmaschine −→ 2-Pushdown-System V
Beispiel: Kopfbewegung nach rechts (Fortsetzung)
Übergang der Turingmaschine (p,a,q,b,R) ∈ δ
Zeichen an der alten Kopfposition lesen und löschen:neuer Übergang (p,a,2, (q,b),ε)Neues Zeichen hinter der neuen Kopfposition einfügen:neuer Übergang ((q,b),c,1,q,bc)... für alle c ∈ Γ
... analog für keine Kopfbewegung (N) oder Kopfbewegungnach links (L)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 26 / 38
Turingmaschine −→ 2-Pushdown-System V
Beispiel: Kopfbewegung nach rechts (Fortsetzung)
Übergang der Turingmaschine (p,a,q,b,R) ∈ δ
Zeichen an der alten Kopfposition lesen und löschen:neuer Übergang (p,a,2, (q,b),ε)Neues Zeichen hinter der neuen Kopfposition einfügen:neuer Übergang ((q,b),c,1,q,bc)... für alle c ∈ Γ... analog für keine Kopfbewegung (N) oder Kopfbewegungnach links (L)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 26 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 27 / 38
2-Pushdown-System −→ 4-Zähler-System I
Ausgangslage
gegeben: 2-Pushdown-System P = (P,Γ′,∆) undKonfigurationen c1,c2
gesucht: 4-Zähler-System Z4 = (Q,∆′) und Konfigurationenc′1,c′2c′2 soll von c′1 aus genau dann erreichbar sein, wenn c2von c1 aus erreichbar ist
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 28 / 38
2-Pushdown-System −→ 4-Zähler-System I
Ausgangslage
gegeben: 2-Pushdown-System P = (P,Γ′,∆) undKonfigurationen c1,c2gesucht: 4-Zähler-System Z4 = (Q,∆′) und Konfigurationenc′1,c′2c′2 soll von c′1 aus genau dann erreichbar sein, wenn c2von c1 aus erreichbar ist
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 28 / 38
2-Pushdown-System −→ 4-Zähler-System II
Vorgehensweise
Simuliere je einen Stack des 2-PDS durch ein2-Zähler-System Z2 = (Q,∆′)Problem: Stack des 2-PDS darf beliebige Zeichenenthalten
Lösung: Codierung!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 29 / 38
2-Pushdown-System −→ 4-Zähler-System II
Vorgehensweise
Simuliere je einen Stack des 2-PDS durch ein2-Zähler-System Z2 = (Q,∆′)Problem: Stack des 2-PDS darf beliebige ZeichenenthaltenLösung: Codierung!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 29 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis k
jedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)
o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System III
Codierung
betrachte k = |Γ|nummeriere Elemente von Γ von 1 bis kjedes w ∈ Γ∗ entspricht dann einer Zahl im (k +1)-erSystem (oberstes Zeichen ist niedrigste Ziffer)o. B. d. A. sei k = 9
Beispiel
Γ = {a,b,c,d,e, f ,g,h, i}iad entspricht 419
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 30 / 38
2-Pushdown-System −→ 4-Zähler-System IV
Operationen
Stackinhalt 419oberstes Zeichen ermitteln
419 mod 10 =
9
Rest der Division durch 10
oberstes Zeichen löschen
419 div 10 =
41
Division durch 10
neues Zeichen x schreiben
419 ·10+ x =
419x
Multiplikation mit 10, Addition des Zeichens
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 31 / 38
2-Pushdown-System −→ 4-Zähler-System IV
Operationen
Stackinhalt 419oberstes Zeichen ermitteln 419 mod 10 = 9Rest der Division durch 10oberstes Zeichen löschen
419 div 10 =
41
Division durch 10
neues Zeichen x schreiben
419 ·10+ x =
419x
Multiplikation mit 10, Addition des Zeichens
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 31 / 38
2-Pushdown-System −→ 4-Zähler-System IV
Operationen
Stackinhalt 419oberstes Zeichen ermitteln 419 mod 10 = 9Rest der Division durch 10oberstes Zeichen löschen 419 div 10 = 41Division durch 10neues Zeichen x schreiben
419 ·10+ x =
419x
Multiplikation mit 10, Addition des Zeichens
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 31 / 38
2-Pushdown-System −→ 4-Zähler-System IV
Operationen
Stackinhalt 419oberstes Zeichen ermitteln 419 mod 10 = 9Rest der Division durch 10oberstes Zeichen löschen 419 div 10 = 41Division durch 10neues Zeichen x schreiben 419 ·10+ x = 419xMultiplikation mit 10, Addition des Zeichens
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 31 / 38
2-Pushdown-System −→ 4-Zähler-System V
Umsetzung
Herausforderung: Implementierung derRechenoperationen
Lösung: Nutze zweiten Zähler als Hilfsvariablealso je ein Zähler für den Inhalt eines Stackes, außerdemein Hilfszähler
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 32 / 38
2-Pushdown-System −→ 4-Zähler-System V
Umsetzung
Herausforderung: Implementierung derRechenoperationenLösung: Nutze zweiten Zähler als Hilfsvariable
also je ein Zähler für den Inhalt eines Stackes, außerdemein Hilfszähler
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 32 / 38
2-Pushdown-System −→ 4-Zähler-System V
Umsetzung
Herausforderung: Implementierung derRechenoperationenLösung: Nutze zweiten Zähler als Hilfsvariablealso je ein Zähler für den Inhalt eines Stackes, außerdemein Hilfszähler
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 32 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 33 / 38
4-Zähler-Systeme −→ 2-Zähler-System I
Überlegung
Ziel: vier Zähler durch zwei ersetzen
Codierung?Primfaktorzerlegung! k = 2k1 ·3k2 ·5k3 ·7k4
Inkrementieren und Dekrementieren durch Multiplikationund Divisionein Zähler zur Durchführung der Operationen (wie oben)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 34 / 38
4-Zähler-Systeme −→ 2-Zähler-System I
Überlegung
Ziel: vier Zähler durch zwei ersetzenCodierung?
Primfaktorzerlegung! k = 2k1 ·3k2 ·5k3 ·7k4
Inkrementieren und Dekrementieren durch Multiplikationund Divisionein Zähler zur Durchführung der Operationen (wie oben)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 34 / 38
4-Zähler-Systeme −→ 2-Zähler-System I
Überlegung
Ziel: vier Zähler durch zwei ersetzenCodierung?Primfaktorzerlegung! k = 2k1 ·3k2 ·5k3 ·7k4
Inkrementieren und Dekrementieren durch Multiplikationund Divisionein Zähler zur Durchführung der Operationen (wie oben)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 34 / 38
4-Zähler-Systeme −→ 2-Zähler-System I
Überlegung
Ziel: vier Zähler durch zwei ersetzenCodierung?Primfaktorzerlegung! k = 2k1 ·3k2 ·5k3 ·7k4
Inkrementieren und Dekrementieren durch Multiplikationund Division
ein Zähler zur Durchführung der Operationen (wie oben)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 34 / 38
4-Zähler-Systeme −→ 2-Zähler-System I
Überlegung
Ziel: vier Zähler durch zwei ersetzenCodierung?Primfaktorzerlegung! k = 2k1 ·3k2 ·5k3 ·7k4
Inkrementieren und Dekrementieren durch Multiplikationund Divisionein Zähler zur Durchführung der Operationen (wie oben)
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 34 / 38
Überblick
Motivation
GrundlagenPushdown-SystemeZähler-SystemeTuringmaschinen
ErreichbarkeitsproblemTuringmaschine −→ 2-Pushdown-System2-Pushdown-System −→ 4-Zähler-System4-Zähler-System −→ 2-Zähler-SystemZusammenfassung
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 35 / 38
Zusammenfassung
Wir können ausgehend von einer Turingmaschine M einZwei-Zähler-System Z mit Konfigurationen c1,c2konstruieren, sodass c2 genau dann von c1 erreichbar ist,wenn M hält.
Wenn das Erreichbarkeitsproblem fürZwei-Zähler-Systeme entscheidbar wäre, wäre daher auchdas Halteproblem für Turingmaschinen entscheidbar.Das ist es aber nicht.Also ist auch das Erreichbarkeitsproblem fürZwei-Zähler-Systeme unentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 36 / 38
Zusammenfassung
Wir können ausgehend von einer Turingmaschine M einZwei-Zähler-System Z mit Konfigurationen c1,c2konstruieren, sodass c2 genau dann von c1 erreichbar ist,wenn M hält.Wenn das Erreichbarkeitsproblem fürZwei-Zähler-Systeme entscheidbar wäre, wäre daher auchdas Halteproblem für Turingmaschinen entscheidbar.
Das ist es aber nicht.Also ist auch das Erreichbarkeitsproblem fürZwei-Zähler-Systeme unentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 36 / 38
Zusammenfassung
Wir können ausgehend von einer Turingmaschine M einZwei-Zähler-System Z mit Konfigurationen c1,c2konstruieren, sodass c2 genau dann von c1 erreichbar ist,wenn M hält.Wenn das Erreichbarkeitsproblem fürZwei-Zähler-Systeme entscheidbar wäre, wäre daher auchdas Halteproblem für Turingmaschinen entscheidbar.Das ist es aber nicht.
Also ist auch das Erreichbarkeitsproblem fürZwei-Zähler-Systeme unentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 36 / 38
Zusammenfassung
Wir können ausgehend von einer Turingmaschine M einZwei-Zähler-System Z mit Konfigurationen c1,c2konstruieren, sodass c2 genau dann von c1 erreichbar ist,wenn M hält.Wenn das Erreichbarkeitsproblem fürZwei-Zähler-Systeme entscheidbar wäre, wäre daher auchdas Halteproblem für Turingmaschinen entscheidbar.Das ist es aber nicht.Also ist auch das Erreichbarkeitsproblem fürZwei-Zähler-Systeme unentscheidbar.
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 36 / 38
Turing-Vollständigkeit
Turing-Vollständigkeit von Zwei-Zähler-Systemen
Beweis bisher: Zwei-Zähler-Systeme könnenTuringmaschinen simulierenAlso: Zwei-Zähler-Systeme sind Turing-vollständig!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 37 / 38
Turing-Vollständigkeit
Turing-Vollständigkeit von Zwei-Zähler-SystemenBeweis bisher: Zwei-Zähler-Systeme könnenTuringmaschinen simulieren
Also: Zwei-Zähler-Systeme sind Turing-vollständig!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 37 / 38
Turing-Vollständigkeit
Turing-Vollständigkeit von Zwei-Zähler-SystemenBeweis bisher: Zwei-Zähler-Systeme könnenTuringmaschinen simulierenAlso: Zwei-Zähler-Systeme sind Turing-vollständig!
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 37 / 38
Quellen
Wolfgang Thomas: Applied Automata Theory.http://drona.csa.iisc.ernet.in/%7Edeepakd/atc-common/wolfgang-aat.pdf
V. Claus, E.-R. Olderog: Informatik III: TheoretischeInformatik.http://proglang.informatik.uni-freiburg.de/teaching/info3/2015ws/material/Kap1-6.pdf
Robin Krahl <[email protected]>, CC-by-sa 4.0
WS 2015/16 Robin Krahl – Zwei-Zähler-Systeme 38 / 38
