Seite 1 von 1

Fragen zur ersten korrigierten Hausübung

Verfasst: 28. Apr 2008 17:47
von peichho
Halo Herr Siegler,

wäre hier der Bereich um seine Fragen zu allen Aufgaben der ersten Hausübung zu stellen?


Wenn ja würde ich gern mit Aufgabe 1.3 anfangen:

zunächst hatte ich überlegt über die rekursive Abzählbarkeit, die man ja nachweisen kann eine Semi-entscheidbarkeit herzuleiten, bin dann allerdings über die semi-entscheidbarkeit von M(quer) gestolpert um die Entscheidbarkeit zu zeigen.

Der nächste Gedanke führte mich zu Satz 7.5 in Verbindung mit Korollar 7.7, da ja entweder M oder M(quer) endlich sein müsste könnte man dadurch die Entscheidbarkeit darlegen. Ein P Programm Decide_M wäre ja dann einfach zu kostruieren.


zu Aufgabe 1.4:

meine frage ist, wie ich hier diagonalisieren sollte? Einen Widerspruchsbeweis in Anlehnung an das Skript wäre mir einleuchtender. Mein Ansatz wäre nun zu sagen, dass sowohl (Phi)n (n) = 8 = (Phi)n+1 (n+1) wäre...aber wie schaff ich mich dann nun weiter voran?

Ich hoffe sie könnten mir ggf ein paar Hilfestellungen geben.


Gruß

Re: Fragen zur ersten korrigierten Hausübung

Verfasst: 29. Apr 2008 10:13
von Simon Siegler
Zu 1.3 ist rekursive Aufzählbarkeit zunächst eine gute Idee. Dafür reicht jedoch ein Teil der gegebenen Eigenschaften. Mit Hilfe der restlichen Eigenschaften sollte es Ihnen dann gelingen, ein Entscheidungsverfahren anzugeben.

Die Diagonalisierung ist ein Widerspruchsbeweis: Man führt die Annahme, eine gegebene Funktion sei in einer gegebenen Aufzählung von Funktionen enthalten, zu einem Widerspruch, indem man zeigt, dass unter dieser Annahme eine Funktion in der Aufzählung sein muss, die sich auf der "Diagonalen" der Aufzählung von jeder Funktion der Aufzählung unterscheidet.
In der dritten Übung wurden ein paar derartige Beweise geführt. Außerdem gibt es in der vierten Übung eine Aufgabe zu Diagonalisierung.

Re: Fragen zur ersten korrigierten Hausübung

Verfasst: 5. Mai 2008 12:33
von jak
Du musst einfach anders diagonalisieren:

du willst wieder hinbekommen, dass deine widerspruchsfunktion einem phi_n0 gleicht um dann auf der Diagonalen [also beim Wert phi_n0(n0) ] einen widerspruch zu bekommen... benutz die charakteristische funktion und tu in deiner widerspruchsfunktion genau das, was sie nicht tut (also 8 wenn nicht 8 und 9 wenn 8 ).