Suche nicht lösbares Problem
Oliver T.
Nicht nur Oberon!
Danke!
--
__________________________________________________________
News suchen, lesen, schreiben mit http://newsgroups.web.de
Andreas Jung
> Welche Probleme sind mit einer Programmiersprache nicht lösbar???
> Nicht nur Oberon!
Beispielsweise das Halteproblem. Es gibt kein Programm, das das
folgende Verhalten aufweist:
Eingabe: * Quelltext einer Prozedur P(x: String)
* String s
Ausgabe: "Ja" wenn der Aufruf P(s) nach endlicher Zeit anhält, also
nicht in eine Endlosschleife gerät. "Nein" sonst.
Der Beweis ist relativ einfach und beispielsweise in der FAQ zur
Newsgruppe de.sci.mathematik zu finden.
Mit Hilfe dieser Unentscheidbarkeit des Halteproblems läßt sich die
Unlösbarkeit vieler weiterer Probleme beweisen. Interessant ist in
diesem Zusammenhang der Satz von Rice, der im wesentlichen besagt,
daß kein "nichttriviales" Problem der folgenden Form entscheidbar,
also algorithmisch lösbar ist:
Eingabe: Quelltext einer Prozedur P(...)
Ausgabe: "Ja" wenn P ein gewisses Verhalten V aufweist, "nein" sonst.
Wenn es Dich interessiert, schicke ich Dir gerne einen Artikel zu,
den ich vor gut zwei Jahren für die "Rostocker Informatik-Berichte"
geschrieben habe. Er stellt zur Unlösbarkeit des Halteproblems und
zum Satz von Rice je einen Beweis mit Struktogrammen, einen mit
Pascal und einen mit Turingmaschinen gegenüber.
Entscheidend ist, daß es hier um "Probleme" in einem mathematischen
Sinne geht. In diesem Sinne sind alle "üblichen" Programmiersprachen
gleichwertig. Fragen hingegen, die darauf abzielen, ob man beispielsweise
"in Oberon die serielle Schnittstelle COM2 ansprechen kann", haben
letztlich nichts mit der Sprache an sich zu tun, sondern lediglich
mit der Implementierung eines bestimmten Compilers.
MfG,
Andreas Jung.
--
Andreas Gisbert Jung ++++++++++++++++++++++++++++++++++++++ DL9AAI
+ mailto:agj...@my-deja.com + http://home.arcor-online.de/agjung +
PGP fingerprint = 03 A3 2D 3A 55 84 0C 43 A6 D7 E1 18 20 9B 7B 21