frage zur theoretischen informatik?

...komplette Frage anzeigen

2 Antworten

"gibts es ein Programm das erkennt ob ein anderes programm funktioniert oder nicht?"

Das Problem nennt sich das "Halteproblem" und gilt als nicht berechenbar, oder fachmännisch ausgedrückt "nicht rekursiv"

https://de.wikipedia.org/wiki/Halteproblem

Falls man die Frage "was ist berechenbarkeit" beantworten sollte, so versuche ich es mit folgender Erklärung: (ACHTUNG: Erklärung sehr grob). Im Grunde genommen versucht man sogenannte "Probleme" mit mathematischen Formel in Form von Programmen/Programmierung zu definieren, so dass eine Maschine die Eingabe akzeptiert und dieses Problem löst. Hierbei sollte immer eine Ausgabe erfolgen, in anderen Worten, dass Programm "terminiert". 

Falls ein Programm nicht terminieren sollte, so nennt man es "nicht rekursiv" bzw. nicht berechenbar. Die Berechenbarkeitstheorie versucht Probleme zu definieren und sie entsprechend der Klasse "rekursiv" oder "nicht rekursiv" zuzuordnen.

Ein Problem welches IMMER terminiert gehört zur Klasse "rekursiv". Falls ein Problem NICHT IMMER terminieren kann dann halt zur "nicht rekursiv".

Diese Erklärung ist sehr grob und nicht 100% richtig definiert und soll nur einen groben Überblick geben.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von testentesten
22.02.2016, 20:26

danke für den antwort, hast du noch irgendwelche ideen für konsequenzen davon, was wäre wenn es so ein programm gäbe?

0

Grundsätzlich gibt es keine Möglichkeit für einen Nachweis, dass ein Programm fehlerfrei funktioniert. Die praktische Überprüfung im einfachen Fall beruht auf Überschaubarkeit. Das ist so wie beim Pilzesuchen im Wald. Selbst wenn man alle Pilze im Korb hat, kann man nicht ausschließen, dass irgenwo versteckt sich doch noch ein Pilz befindet. Fehler können in ausschließlich selten vorkommenden Fällen auftreten. Ich hatte mal eine Prüfung auf Eingabefehler, die nach zehn Jahren regelmäßiger Anwendung einen Eingabefehler nicht erkannt hat. Vorher hatte nie jemand dieses unzulässige Zeichen versehentlich eingegeben. In komplexen Systemen, wie etwa bei der NASA, werden spezielle Simulationsumgebungen zum Testen der Programme verwendet. Beim Herstellen von CPU-Chips bei Intel wird der künftige Chip auf Softwareebene nachgebildet und der Test simuliert. Erst wenn dieser Test abgeschlossen ist, geht der Chip in die Fertigung. Trotzdem hat es schon Fehler gegeben, die sich im Nachhinein herausgestellt haben. Ich selbst hatte jahrelang an einem Programm gearbeitet, das in monatlicher Folge Eingabedaten auf sehr komplexe Weise verarbeitet hat. Dieses Programm wurde ständig erweitert und es bestand die Gefahr, dass neu eingebaute Funktionen Auswirkungen auf bereits getestete und funktionierende Programmteile hatten. Ich habe mir damals ein Testsystem erstellt, bei dem ein bestimmtes Eingabepaket sowohl mit der alten als auch neuen Version des Programmes verarbeitet wurde und das Ergebnis der beiden Läufe maschinell auf Gleichheit überprüft wurde. Bei Differenzen, die gar nicht so selten festgestellt wurden, konnte man dann gezielt der Ursache nachgehen und den Fehler beheben.


Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?