Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Halteproblem - Beweis

0 Pluspunkte 0 Minuspunkte
122 Aufrufe

Hallo zusammenn,

ich habe ein kleines Verständnisproblem zum Beweis des Halteproblems:

Weshalb reicht es auch, eine einzige Beweisturingmaschine (BT) zu finden, die unter der Eingabe des Halteproblems nicht anhält?

Danke im Voraus für eure Hilfe!

Gefragt 9 Feb in BER-AA von uovhe uovhe Lernwillige(r) (290 Punkte)  

Eine Antwort

0 Pluspunkte 0 Minuspunkte
Das ist ein Beweis durch Gegenspruch... man behauptet es gäbe eine TM, die hält, da diese (allgemeine) jedoch nicht hält haben wir bewiesen, dass das Halteproblem nicht lösbar ist.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)
Beantwortet 9 Feb von unort unort Eins-Komma-Null-Anwärter(in) (3,890 Punkte)  
...