Das Halteproblem - kann es jamand erklären?

HI,

wir müssen in Info grad einen Vortrag über das Halteproblem machen.
Und da wollte ich fragen ob mir das jemand erklären kann, der damit schon
mal etwas zu tun hatte, denn bei den ganzen hochwissenschaftlichen Sätzen bei
Wikipedia blick ich irgendwie nicht ganz durch.
Ich hab mich schon bis zum Beweiß das es keine Turingmaschine gibt, die das
Halteproblem beweißen kann durchgearbeitet, aber da komm ich jetzt einfach nicht
weiter. Ich hab mir das glaub ich schon 10x durchgelesen und versteh immer noch
Bahnhof.
Wäre nett wenn mir das jemand erläutern könnte...

MfG & Thx Bergmann.

Ich fuerchte es ist nicht ganz einfach dir das per Text zu erklaeren.

das es keine Turingmaschine gibt, die das Halteproblem beweißen kann

Zum Vergrößern anklicken....

Das bezieht sich nicht auf eine TM, sondern auf die Allgemeinheit von TMs - fuer eine spezielle laesst sich das pruefen.

Vielleicht eine kleine Hilfe es zu verstehen:
Stell dir vor ich bin die TM welche du testen willst, du kannst dazu mich immer wieder fragen ob ich angehalten habe. Darauf antworte ich jedesmal mit Ja oder Nein.

1. Nein
2. Nein
3. Nein
4. ?

Was antworte ich bei 4.?

Bestimmt auch "Nein", oder ?!

Wenn ich das in dem kurzen Moment richtig verstanden habe, geht es in etwa um folgendes:

Stell dir vor, du fragst gerade eine beliebige Person, ob sie mit dir spricht (unter der Bedingungen, das sie nur "Ja" und "Nein" als Antwort geben kann). Sie kann dementsprechend theoretisch niemals "Nein" sagen, weil sie ja mit dem Moment der Antwort mit dir spricht, also "Ja". [bzw., in deinem Fall: "Nein"]

Nicht schlagen wenns falsch is

Hi,

hatten wir dich nicht schon mal hier mit der Frage nach der Berechenbarkeit?

Ich bin in der 13. Klasse eines Gymnasiums und unser Informatiklehrer hat ein Skript dazu ins Internet gestellt.

Hier der Link:

http://www.mohr-netz.de/Informatik/...ische_Informatik/theoretische_informatik.html

Mfg Chuckyy

@Bergmann89
Du hast die Frage eigentlich beantwortet, du weisst nicht was ich dir Antworte. So aehnlich verhaelt sich auch der Beweis, du kannst eben im Allgemeinen nicht sagen ob die TM anhaelt oder eben nicht. Die TM koennte nach 1 Sekunde anhalten, aber auch erst in einem Jahr, in 2^238947234 Millionen Jahren oder gar nicht.

@AndrewPoison
So meinte ich das nicht, sprechen tu ich in jedem Fall mit der Person. Es ist eher eine Funktion, welche dir sagt ob ich, die TM, eben noch laufe oder schon angehalten habe. Oder ich hab dich jetzt falsch verstanden.

@Chuckyy
Nein, Berechenbarkeit und Entscheidbarkeit sind zweit unterschiedliche Dinge.

Also das ist an Sich ein ganz schön haariges Problem, was du diskutieren willst. Um das zu verstehen, müsstest du erstmal die "Mächtigkeit von (unendlichen) Mengen" verstehen. In der Informatik spielt dabei die Potenzmenge eine besondere Rolle.

Der Hintergrund ist die Entscheidung, ob ein anderes Programm entscheiden kann, ob ein anderes nach endlich vielen Schritten die Rechnung beendet hat, oder nicht (bei gegebener Eingabe) (allerdings muss das für ein beliebiges (!) Programm gelten).
Ein Program macht nichts anderes, als die Menge der Eingabe-Werte auf die Menge der Ausgabewerte abzubilden.
Mit anderen Worten: Nicht jedes Element in der Ausgabemenge kann eindeutig einer Eingabe zugeordnet werden (Potenzmenge ist mächtiger als die Eingabemenge, wenn ich das richtig in Erinnerung habe). Die Abbildungen von den Eingaben zu den Ausgaben sind zwar injektiv, aber nicht bijektiv (also nicht surjektiv). Also musst dich mal kurz mit Abbildungen auseinandersetzen

Ich empfehle mal ein tiefergehendes Buch zu benutzen als nur wiki. Ich bin mir da auch nicht mehr so sicher, da ich mit den Abbildungs-Zeugs nichts mehr zu tun habe.

Hast du überhaupt mal versucht, selbst außer auf wiki zu suchen? Z.B. >>hier<<