BuL Arithmetische Hierarchie

Praktikant

Date of registration: Mar 12th 2005

Monday, July 24th 2006, 1:58pm

Hallo ich habe zwei Fragen zu dem Bereich "Arithmetische Hierarchie" von der Vorlesung BuL:

1.) Was kann ich mir genau unter der Folge {Leere Menge}', {Leere Menge}'', {Leere Menge}''', ..., {Leere Menge}(i) vorstellen?? Also {Leere Menge}' entspricht ja dem speziellen Halteproblem. Das bedeutet ich habe eine OTM mit leerem Orakel. Dies entspricht ja einer "normalen" TM (ohne Orakel) und die Aussage, dass K nicht entscheidbar ist aber rekursiv aufzählbar, passt. Wie muss ich mir das nun z.B. mit {Leere Menge}'' oder {Leere Menge}''' vorstellen??

2.) Was haben in der Abbildung zur arithmetischen Hierarchie die diagonalen Verbindungen zwischen den Klassen zu bedeuten?? Ist da noch etwas besonderes in den Schnittpunkten der Diagonalen??

Vielen dank schon einmal im voraus.

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Monday, July 24th 2006, 2:15pm

RE: BuL Arithmetische Hierarchie

Quoted

Original von HELP
Hallo ich habe zwei Fragen zu dem Bereich "Arithmetische Hierarchie" von der Vorlesung BuL:

1.) Was kann ich mir genau unter der Folge {Leere Menge}', {Leere Menge}'', {Leere Menge}''', ..., {Leere Menge}(i) vorstellen??

Den Operator ' nennt man Turing Jump. Ist A eine Menge, so ist A' die Menge der Kodierungen aller Orakel-Turingmaschinen, die mit Orakel A bei ihrer eigenen Kodierung als Eingabe anhalten.

Da eine Orakel-TM mit der leeren Menge als Orakel einer "normalen" TM entspricht, ist [img]http://mimetex.selke.info/?\emptyset'[/img] das Halteproblem.

Der Jump Operator dient also dazu, aus einer Menge eine "echt unberechenbarere" zu konstruieren. Das zeigt sich dann in der Parallelen zur arithmetischen Hierarchie.

Quoted

2.) Was haben in der Abbildung zur arithmetischen Hierarchie die diagonalen Verbindungen zwischen den Klassen zu bedeuten?? Ist da noch etwas besonderes in den Schnittpunkten der Diagonalen??

Die Verbindungen bedeuten "ist Teilmenge von". Die Kreuzungspunkte der Diagonalen haben also keine besondere Bedeutung.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Jul 24th 2006, 2:16pm)

Go to the top of the page

HELP

Praktikant

Posts: 17

Date of registration: Mar 12th 2005

3

Monday, July 24th 2006, 2:40pm

Vielen dank für die schnelle Antwort :-)

Go to the top of the page

HELP

Praktikant

Posts: 17

Date of registration: Mar 12th 2005

4

Monday, July 24th 2006, 4:13pm

Ich habe noch mit der Kleinigkeit ein Problem, dass im Skript im vorletzten Korollar des 8. Kapitels unter (iv) steht, dass Pi(i-1) keine Teilmenge von Sigma(i) ist. Damit dürften die diagonalen Verbindungen in der Abbildung ja nicht stehen...
Oder ist das ein Fehler im Skript (Korollar)??

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

5

Monday, July 24th 2006, 4:45pm

Quoted

Original von HELP
Ich habe noch mit der Kleinigkeit ein Problem, dass im Skript im vorletzten Korollar des 8. Kapitels unter (iv) steht, dass Pi(i-1) keine Teilmenge von Sigma(i) ist.

Das ist ein Tippfehler, gemeint ist "echte Teilmenge". Das geht aber aus dem obigen Satz (auf den sich das Korollar bezieht) klar hervor. Also schau Dir den lieber nochmal genau an.