algorithmus < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:03 Do 04.11.2004 | | Autor: | SUNNY000 |
hi leute, die letzte frage hab ich doch noch gelöst, aber wie sieht es mit algorithmus aus? Ich muss überlegen, ob es einen algorithmus geben kann, mit dem für beliebige programme entschieden werden kann, ob man jemals eine ausgabe liefert oder nicht. Das ist die aufgabe und ich verstehe sie überhaupt nicht.
|
|
| |
|
Hallo sunny!
> hi leute, die letzte frage hab ich doch noch gelöst, aber
> wie sieht es mit algorithmus aus? Ich muss überlegen, ob es
> einen algorithmus geben kann, mit dem für beliebige
> programme entschieden werden kann, ob man jemals eine
> ausgabe liefert oder nicht. Das ist die aufgabe und ich
> verstehe sie überhaupt nicht.
Also, stell dir vor, dein Rechner rechnet und rechnet und rechnet und hört einfach nicht mehr auf zu rechnen. Nun fragst du dich: ist der jetzt abgestürzt oder passt die Eingabe nicht so zu dem Algorithmus, dass dieser terminiert und der Rechner somit bis in alle Ewigkeit weiterlaufen wird?
Und damit du dich das nicht fragen musst, sollst du eine Maschine oder einen Algorithmus entwickeln, der dir für dein Programm und deine Eingabe entscheidet, ob der Rechner jemals eine Ausgabe gibt. Diese Maschine berechnet dir keine Lösung, sondern sagt nur, ob der Algo terminiert oder nicht!
Sofern ich das jetzt nicht falsch verstanden habe, ist das das sogenannte[b] [mm] Halteproblem[\b]. [/mm] Und dafür kann man beweisen, dass es keinen Algorithmus gibt, der dein Problem löst. Wie man das beweist, das hat mich allerdings noch nicht so sonderlich interessiert, müsste aber in Büchern zu finden sein.
Und hier noch ein schöner Link, der dir das vielleicht auch noch veranschaulichen kann, wenn meine Erklärung dir nicht reichte:
![[]](/images/popup.gif) klicke hier und gucke unter "Theorie"
Viele Grüße
Bastiane
|
|
|
|
