Wenn das Halteproblem entscheidbar wäre ...
-
... dann könnte man doch die Riemannsche Vermutung ganz einfach beweisen, indem man ein Programm schreibt, das nach Verstößen gegen die Vermutung sucht. Dann steckt man das Programm in den Halteproblem-Entscheider. Wenn der sagt, dass das Programm endlos läuft, dann gilt die Riemannsche Vermutung.
Dasselbe gilt für die Goldbachsche Vermutung!Also lasst es uns versuchen! Auch wenn die Beweise sagen, dass es nicht möglich ist!
-
Um die riemannsche Vermutung zu widerlegen, müsste man überabzählbar viele Zahlen durchtesten, und allein zum Aufzählen all dieser Zahlen gibt es keinen Algorithmus (weil die Menge eben nicht abzählbar ist :)).
Bei der Goldbachschen Vermutung kann man allerdings einen Algorithmus bauen, der den "Verstoß" (nach endlicher Zeit) findet, falls er denn auftritt.Die Fragestellung ist aber trotzdem völlig sinnlos.
PS: hast du das von hier? http://www.gk-informatik.de/algo/halt.html#www
-
Der Beweis den ich kenne, der gegen die Existenz eines Halteproblem-Algorithmus spricht, funktioniert dadurch, dass man dem Algorithmus seinen eigenen Code gibt. Könnte man das nicht einfach verbieten?
-
phalanx-fanboy schrieb:
Der Beweis den ich kenne, der gegen die Existenz eines Halteproblem-Algorithmus spricht, funktioniert dadurch, dass man dem Algorithmus seinen eigenen Code gibt. Könnte man das nicht einfach verbieten?
nicht ganz: http://de.wikipedia.org/wiki/Halteproblem#Beweis
-
Qbert² schrieb:
... dann könnte man doch die Riemannsche Vermutung ganz einfach beweisen...
Erstens: Gewohne Dir mal ab, vom Titel aus in den Text einfach weiterzuschreiben.
Zweitens: Wenn {falsche Aussage}, dann kann man damit {beliebige Aussage} beweisen. Deine Idee ist davon nur ein Spezialfall.