Beweis "Mehr Probleme als Programme"
lima-city → Forum → Sonstiges → Off-Topic
ansatz
bestehen
beweis
bug
computer
computerprogramm
definition
formalismus
funktion
gleichung
http
informatik
maschine
menge
problem
programm
teilmenge
url
zahl
zeigen
-
Servus,
mein Informatik-Lehrer sagte irgendwann mal, dass es einen mathematischen Beweis dafür gäbe, dass es "weniger theoretisch mögliche Computerprogramme als theoretisch Mögliche Probleme" gäbe, was heißt, dass es "Probleme geben muss, die ein Computer nicht lösen kann und nie lösen wird"...
Ich hab ne weile herumgegoogled, aber solch einen Beweis nirgends gefunden... scheint also ein insider zu sein :D
Jedenfalls würde mich diese Theorie sehr interessieren.. Kennt jemand diesen Beweis zufällig?
Beitrag zuletzt geändert: 15.9.2010 16:46:02 von velima -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Ganz einfach: Für ein Programm braucht es eine hochkomplizierte Reihe von Einsen und Nullen (genauer: leitend oder nicht leitend, Flachland oder Hügel, Flachland oder Einkerbung, Nordpol oder Südpol, je nach Datenträger). Es gibt mathematisch gesehen relativ wenige Programme für einen Computer, die fehlerfrei laufen. Die Zahl steigt drastisch in die Höhe, sobald auch Programme mit Fehlern erlaubt sind und geht in richtig hohe Zahlengebiete (Zahlen mit höheren Dezimalstellen, als du Zahlen schreiben kannst), wenn es keine Programme sind, sondern einfach nur Schrott.
-
ganz einfacher Lösungsansatz:
wenn ein Problem besteht, wird ein Programm geschrieben... durch dieses programm entstehen wieder andere Probleme, die gelöst werden müssen... auch dafür schreibt man programme...
wenn man es aufs mindeste abstrahierst, kommt raus:
1 Problem= 1Programm + x*problem
stell das nach x um und du weißt, in welchem Verhältnis zu den Programmen Probleme bestehen^^ -
Außerdem sitzt das größte Problem meist vor der Tastatur. Und das meist im ungekehrter Hirachie. Was da so teilweise, Problemen gemeldet wird ist schon beachtlich. Am schönsten finde ich aber immer noch die besonders in Chef-Etagen beliebte vergessen Diskette im Laufwerk.
-
ist doch logisch das man mit mehr programmen mehr probs hat.
ich mein die chance das ein programm mal fehler hat steint mit jedem programm
aber die win98 zeiten sind vorbei mit xp und win7 und allerhand open source software wo "die halbe welt" in den sourcecode schaut und mitprogrammiert gibts doch kaum noch probelme mit software.
ich hab die erfahrung gemacht das je komplizierter die programme sind imso eher haben sie bugs - auch logisch. moderne 3d spiele kommen leider für den pc zusätzlich sehr häufig unfertig auf den mark und die 1.0 enthöt bugs ohne ende die dann nachgepatcht werden -
velima schrieb:
... mein Informatik-Lehrer sagte irgendwann mal, dass es einen mathematischen Beweis dafür gäbe, dass es "weniger theoretisch mögliche Computerprogramme als theoretisch Mögliche Probleme" gäbe, was heißt, dass es "Probleme geben muss, die ein Computer nicht lösen kann und nie lösen wird"...
Dass es Probleme gibt, die ein Computer nicht lösen kann(weil sie prinzipiell unlösbar sind), ist schon lange bewiesen.
Im Prinzip wurde dies bereits 1931 durch Kurt Gödel bewiesen (also in einem Zeitalter, als es noch gar keine Computer gab), und zwar durch seinen Unvollständigkeitssatz (siehe Wikipedia-Artikel dazu)
Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.
Als Beispiel kann man die Prädikatenlogik 1. Stufe nehmen, die erwiesenermaßen unvollständig ist.
Hieraus ergibt sich (für eingehendere Lektüre bitte Fachliteratur konsultieren) folgender Sachverhalt:
Es ist (umgangssprachlich formuliert) unmöglich, allein aus der Struktur einer Formel heraus zu entscheiden, ob sie gültig ist oder nicht. =>Folglich kann es auch kein Computerprogramm geben, das dies tut.
Später hat Allan Turing, ein Pionier der theoretischen Informatik einen Formalismus gefunden, mit dem man alle möglichen Algorithmen beschreiben kann, die sogenannte Turing-Maschine.
Für diesen Formalismus gibt es ein klassisches (übrigens vollkommen wohldefiniertes) Problem, das prinzipiell unlösbar ist, und zwar das Halteproblem.
Gegeben sei eine Turingmaschine T1 mit beliebig vielen Zuständen.
Nun gibt es hierfür keine Turingmaschine T2, die für jede Turing-Maschine T1 in einer endlichen Zeit entscheidet, ob T1 hält oder nicht.
Dieses Halteproblem wiederum ist die Basis für eine ganze Problemklasse, und zwar die Klasse der Probleme, die sich auf dieses Halteproblem reduzieren lässt (d.h. es lässt sich beweisen, dass sich dieses Problem auf das Halteproblemzurückführen lässt).
Sogar wohldefinierte Funktionen gibt es, die man nicht allgemein ausrechnen kann (folglich gibt es auch keinen Algorithmus, den man für einen Computer schreiben könnte).
Beispiel: die "busy-beaver-Funktion" . Mehr siehe auf wikipedia.
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
