Diagaonaliserungsbeweis-> semi-entscheidbar (Turingmaschinen)?

Hi, kann mir wer erklären wie genau der Diagonalisierungsbeweis funktioniert, verstehe diesen noch nicht ganz:

Also, ich verstehe nicht ganz warum dies am Ende ein Widerspruch ist dann. Ist es so gemeint, dass wir ja anfangs mit der Turingmaschine R die Diagonale definiert haben und dann mit D die R nutzt , grad das Gegenteil auf dieser Diagonalen stehen muss, was ja nicht gehen kann?

Gruß

Answer 1

[PWolff]

An der Aufgabenstellung finde ich etwas irreführend, dass auf der Diagonalen "ja" und "nein" abwechseln, was suggeriert, dass die M_i entsprechend sortiert wären. (Bei überabzählbar vielen Maschinen - was ja wohl der Fall ist - ist der Beweis, dass eine solche Sortierung existiert, ziemlich haarig, falls überhaupt möglich.)

Und schon die Diagonalisierung selbst finde ich irreführend - wir benötigen ja nur einen einzigen Eintrag, der (zufällig) auf der Diagonalen liegt, nämlich D(<D>). (Bei anderen Diagonalverfahren ist es entscheidend, dass man sämtliche Diagonalelemente verwendet.)

-----

Letztlich läuft es auf eine aussagenlogische Aussageform der Form

p => ( (q => NICHT q) UND (NICHT q => q) )

hinaus. Daraus folgt dann NICHT p.