Halteproblem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:11 Mi 04.11.2009 | | Autor: | vju |
| Aufgabe | Überlegen Sie, ob es einen Algorithmus A(P) geben kann, der für beliebige Programme P entscheidet, ob sie jemals eine Ausgabe liefern oder nicht.
Führen Sie das Problem dazu geeignet auf das Halteproblem zurück: Gegeben ein beliebiges Programm P. Können Sie es so in ein anderes Programm P' umformen oder einbetten, dass mit A(P') das Halteproblem H(P) gelöst würde.
Grob formuliert ist das Halteproblem die Frage, ob ein beliebiges Programm P terminiert.
Das Halteproblem ist unentscheidbar: D.h. es gibt keinen Algorithmus H(P), der zu jedem
beliebigen Programm P berechnet, ob dieses terminiert oder nicht. |
Hallo,
Ich weiß nicht so recht wie ich diese Aufgabe rangehen soll. Wie das Halteproblem jetzt funktioniert habe ich mir bei Wikepedia angeschaut und denke ich auch verstanden.
Aber was hat das Halteproblem denn hier mit der Frage ob eine Ausgabe geliefert wird oder nicht zu tun? Muss der Algorithmus anhalten, damit etwas ausgegeben wird?
Hoffe mir kann jemand einen kleinen Hinweis darauf geben.
Liebe Grüße
Vju
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Fr 06.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
