Fragen zur ersten korrigierten Hausübung

peichho
Neuling
Neuling
Beiträge: 4
Registriert: 6. Mai 2007 23:00

Fragen zur ersten korrigierten Hausübung

Beitrag von peichho » 28. Apr 2008 17:47

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ß

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Fragen zur ersten korrigierten Hausübung

Beitrag von Simon Siegler » 29. Apr 2008 10:13

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.

jak
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Nov 2004 15:42
Kontaktdaten:

Re: Fragen zur ersten korrigierten Hausübung

Beitrag von jak » 5. Mai 2008 12:33

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 ).

Antworten

Zurück zu „Archiv“