Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Hier könnt ihr euch über die Inhalte der Übungsblätter austauschen und Fragen stellen.

Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon PeterW » 27 Jan 2014, 04:40

Hallo Leute,

In der Vorlesung hat Professor Smolka die Beweisart mittels Reduktion verwendet,
um Aufgabe 1, d) zu zeigen.
Ich habe diese Beweisart nicht so richtig verstanden..

Zeige: ~Hy ist nicht akzeptierbar. (wobei natürlich das ~ unser Komplement beschreiben soll)

(Reduktion: "~H <= ~Hy" (so wurde diese als Kommentar angeführt))

Zu Beginn unseres Beweises machen wir folgende Annahme, ich vermute für einen Widerspruchsbeweis:
Sei ~Hy akzeptierbar => Dann gibt es ein u aus Sigma*, dass unsere Sprache ~Hy akzeptiert.

Dann gilt aus unserer Definition:

Für alle x aus Sigma*. pi(u,x) <=> x ist nicht Element aus Hy <=> ~pi(x,y)

Bis hierhin ist mir alles noch klar.

Aber anschließend nutzten wir nun die Reduktion und sagten:
Es genügt zu zeigen:
x ist in ~H <=> pi [A alpha. y @ A beta. alpha @ alpha] x (A = Lambda)

Ich habe nun folgende Fragen:
1) Was genau sagt uns die Reduktion hier bzw. was bringt sie uns?
Ich merke, dass wir ~Hy auf ~H zurückführen möchten, für die wir bereits
mittels Diagonallemma gezeigt haben, dass sie nicht akzeptierbar ist.
Wieso dürfen wir eine Annahme machen?
2) Ich hätte einen Widerspruchsbeweis erwartet.
Jedoch endete der Beweis mit einer Äquivalenz und von Widerspruch war
weit und breit nichts zu sehen.
Hängt dies mit der Reduktion zusammen oder war der Beweis noch unvollständig?

Mit freundlichen Grüßen
Peter
PeterW
 
Beiträge: 8
Registriert: 19 Okt 2013, 19:53

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon jkaiser » 27 Jan 2014, 09:01

Hallo Peter,

die ersten 90% des Beweises hast du sehr gut erkannt. Hier nochmal die konkrete Übersicht eines Reduktionsbeweises für Akzeptierbarkeit:

Für Sprachen A und B führen wir die Reduktion (A <= B).
  • Wir wissen A ist nicht akzeptierbar (1).
  • Wir nehmen an, dass B akzeptierbar wäre (und leiten daraus einen Widerspruch ab)
  • Sei u der Akzeptor für B.
  • Wir geben nun einen konkreten Akzeptor v für A an. (Dies sollte nur möglich sein, weil wir annehmen, dass wir ein u mit bestimmten Eigenschaften haben)
  • v akzeptiert A, was in direktem Widerspruch zu (1) steht. Folglich kann B nicht akzeptierbar sein. QED
Um Akzeptoren, bzw. generell Programm zu beschreiben nutzen wir die Programmiersysteme zusammen mit Ausdrücken, die eine minimale funktionale Programmiersprache darstellen. Ggf. muss man natürlich entsprechende Negationen in obigen Beweis einfügen.

Was den konkret genannten Beweis angeht, müsste dir jetzt eigentlich klar sein, was hier der Akzeptor v ist. Andernfalls einfach nochmal fragen ;-)

Gruß
Jonas
jkaiser
 
Beiträge: 17
Registriert: 13 Okt 2013, 16:50

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon PeterW » 27 Jan 2014, 12:45

Hallo Jonas,

Also, ich denke, ich habe den Akzeptor v für unser A, also unsere Sprache ~H, bereits angegeben:

v = [A alpha. u @ A beta. alpha @ alpha] (A = Lambda)

Hier verwenden wir ja unser u, ich weiß aber nicht genau, welche Eigenschaft wir von diesem dabei ausnutzen.

Zumindest kann man nun weiter zeigen:

x ist Element von ~H = pi v x

Also haben wir einen Akzeptor v für die Sprache ~H und können nun beweisen,
dass dieser die Sprache ~H auch tatsächlich akzeptiert:

x ist Element von ~H = pi [A alpha. u @ A beta. alpha @ alpha] x
= pi [u @ A beta. x @ x] epsilon (nach Regel für Ausdruck, 6. auf dem Blatt)
= pi [u] [A beta. x @ x] (nach Regel für Ausdruck, 5. auf dem Blatt)
= pi u [A beta. x @ x] (nach Regel für Ausdruck, 1. auf dem Blatt)

Nun hatte ich bereits oben erwähnt:
Für alle x aus Sigma*. pi u x = ... = x ist Element von ~Hy = ~ pi x y
Wir setzten: x = [A beta. x @ x] und somit gilt:

... = ~ pi [A beta. x @ x] y
= ~ pi [x @ x] y (nach Regel 6)
= ~ pi [x] [x] (nach Regel 5)
= ~ pi x x (nach Regel 1, 2x)
= x ist Element von ~H (folgt aus Definition von H bzw. ~H)

Somit akzeptiert v die Sprache ~H. => Widerspruch!

Nutzt man nun diese eingebaute Eigenschaft (die ich wie gesagt noch nicht erkenne) von u aus,
so können wir schlussfolgern, dass ~Hy nicht akzeptierbar ist und sind somit fertig.

Liebe Grüße
Peter
PeterW
 
Beiträge: 8
Registriert: 19 Okt 2013, 19:53

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon tegi » 27 Jan 2014, 18:56

Hallo,

wie kommt man eigentlich auf diesen konkreten Akzeptor? Ich glaube, ich habe noch nicht ganz verstanden, was es überhaupt bedeutet, wenn x y akzeptiert, also π x y. Was bedeutet das genau und wie kommt man dann auf diesen Akzeptor?

Danke und Grüße,
Tobias
tegi
 
Beiträge: 3
Registriert: 26 Jan 2014, 13:56

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon jkaiser » 27 Jan 2014, 19:38

@ Peter:

die "ominöse Eigenschaft" von u hast du bereits ausgenutzt als du

pi u [...]

durch

- pi [...] y

ersetzt hast.

@ Tobias: Der Akzeptor ist einfach ein simples funktionales Programm in der sehr limitierten Sprache, die wir Ihnen im Kontext der Programmiersystem zur verfügung stellen. Sie sollten sich die Semantik genau ansehen um zu verstehen, wie die einzelnen Konstrukte arbeiten. Konkret bedeutet pi x y , dass ein universelles Berechnungssystem (z.B. eine Turing Maschine) das Programm x ausführt, mit der Eingabe y und dann terminiert mit einer positiven Rückmeldung. Im Fall einer TM heißt dies, dass die Maschine den Zustand t erreicht hat. Wie genau man eine TM baut die belibige andere TMs auf beliebigen EIngaben ausführt, bleibt aber im Rahmen dieses Kurses unterhalb der Abstraktionsebene, die wir betrachten (darum die Programmiersystem).

Ich hoffe dass macht die Sache etwas klarer.
Mfg
Jonas
jkaiser
 
Beiträge: 17
Registriert: 13 Okt 2013, 16:50

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon tegi » 27 Jan 2014, 19:53

Hallo,

das macht es tatsächlich ein wenig klarer, aber ich verstehe immernoch nicht, warum λα.u#λβ.α#α ein simpler Akzeptor sein soll. Also warum akzeptiert dieses Programm x, wenn u x akzeptiert? Ich schaffe es zumindest nicht, π [λα.u#λβ.α#α] x in π u x umzuformen.
tegi
 
Beiträge: 3
Registriert: 26 Jan 2014, 13:56

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon m.zeimet » 27 Jan 2014, 21:22

Lässt sich [λα.u@λβ.α@α] verstehen als:
Es gibt eine "Maschine" u, die für Input α die "Maschine", die als "Maschine" eben dieses α besitzt, α akzeptiert? :shock:
Was dann (vielleicht) soviel heißt wie "Ich bau mir ne Maschine A, die ne Maschine B auf den Input X anwendet. Maschine B tut nun X als Maschine Verwenden und testen(ausgeben) , ob also X dann X akzeptiert." A ist dann = ~Hy , B = ~H.
Ich rate mal mehr oder weniger und sage der Beweis läuft dann ungefähr so:
Durch die Annahme weiß ich, dass es so eine Maschine A gibt (geben soll ;) ). Wenn es nun ne so definierte akzeptierende Maschine A gibt, muss es auch ne akzeptierende Maschine B geben. Da es Maschine B aber (unabhängig von Input X) nicht geben kann, da man das vorher schon bewiesen hat, kann es kein Maschine A geben, dann auch unabhängig von Input X. ( Hier würde man dann A auf B reduziert haben?)
Somit wär der oben genannte Akzeptor dann auch der simpelste, da er ja am allgemeinsten gehalten ist, und somit logischerweise keine bestimmte (nicht simple) Spezifikation enthält.
Hab ich es richtig verstanden oder grad kompletten Müll geschrieben? :D
m.zeimet
 
Beiträge: 4
Registriert: 16 Okt 2013, 14:24

Re: Übungsblatt 12, Aufgabe 1 (Beweise mittels Reduktion)

Beitragvon jkaiser » 29 Jan 2014, 20:41

@ tegi: Das argument läuft wie folgt:
  1. Die Anwendung der sematischen Regeln/Bedingungen bei λ und @: π [λα.u@λβ.α@α] x ≡ π [u@λβ.x@x] e ≡ π u [λβ.x@x]
  2. Laut Annahme weißt du: ∀x. π u x ≡ ¬ π x y
  3. Insbesondere also auch (All-Quantor!): π u [λβ.x@x] ≡ ¬ π [λβ.x@x] y

Von hier aus sollte es einfach sein.

@ m.zeimet:
  1. u ist ein Programm, also ein Wort, dessen Existenz angenommen wird um einen Widerspruch zu bauen. u erfüllt die Eigenschaft: ∀x. π u x ≡ ¬ π x y
  2. [λα.u@λβ.α@α] ist ebenfalls ein Programm/Wort welches u als "Teilprozedur" verwendet.
  3. Die Struktur dieses "Wrapper Programms" beschreiben wir mithilfe von Ausdrücken, die äußeren Klammern sind wichtig, damit der Typ stimmt. In Worten: Das Programm nimmt seine Eingabe x und führt dann das Programm u mit der Eingabe [λβ.x@x] aus. Wir wissen zwar nicht wie u intern konkret aussieht, aber wir kennen eine EIgenschaft von u, und diese besagt, dass wenn wir die Eingabe von u selbst als Programm laufen lassen und diesem y als Eingabe geben, dass die Maschine dann nicht akzeptiert. Jetzt haben wir das inenre Programm so konzipiert, dass es seine EIngabe sofort verwirft, i.e. das y und x einfach auf sich selbst anwendet.
  4. Anhand dieser recht verbosen Darstellung sollte es einleuchten weshalb wir die logische Notation bevorzugen und von einer konkreten Maschinendarstellung abstrahieren wollen.

Sollten auf jeden Fall mit Äquivalenzen, Gleichungen, Quantoren und boolschen Operationen arbeiten können!
jkaiser
 
Beiträge: 17
Registriert: 13 Okt 2013, 16:50


Zurück zu Übungsblätter

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 0 Gäste

cron