Entscheidungsproblem < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:25 Di 10.06.2008 | | Autor: | Gilga |
Ich bin durch die wikipedia etwas verwirrt.
Dort(de und en) wird es so dargestellt als ob Chruch und Turing gezeigt hätten, dass es kein Verfahren gibt um zu zeigen ob eine Aussage wahr ist.
Tatsächlich folgt dies ja bereits von Gödels unvollständigkeitssatz und Turing und Church zeigten es gibt kein Verfahren um festzustellen ob eine Aussage beweisbar ist oder nicht.
Oder liege ich da falsch?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:36 Do 12.06.2008 | | Autor: | Gilga |
Kein sich denn keiner motivieren?
|
|
|
| |
|
... dass es kein Verfahren gibt um zu
zeigen ob eine Aussage wahr ist.
So kannst du das nicht sagen. Die Aussage "Jede durch 4 teilbare Zahl ist auch durch 2 teilbar" könnte bezweifelt werden, da "es kein Verfahren gibt um zu
zeigen ob diese Aussage wahr ist."
Tatsächlich hat Gödel gezeigt, "dass in einem widerspruchsfreien Axiomensystem, das genügend reichhaltig ist, um die Arithmetik (natürliche Zahlen) in der üblichen Weise aufzubauen und das überdies hinreichend einfach ist, es immer Aussagen gibt, die aus diesem weder bewiesen noch widerlegt werden können."
Das heißt nicht, dass man keine Aussage als wahr oder falsch erkennen kann, sondern nur, dass es überhaupt solche Aussagen gibt. Hierzu ein Beispiel:
Es ist [mm] 3^2+4^2=5^2 [/mm] und auch [mm] 12^2+5^2=^3^2. [/mm] Die Zahlen 3, 4 und 5 bzw. 12, 5 und 13 nennt man pythagoräische Drillinge (oder Tripel).
Der berühmte Mathematiker Pierre de Fermat hat nun behauptet, dass es keine drei natürlichen Zahlen a, b und c gibt, für die [mm] a^n+b^n=c^n [/mm] gilt wenn n eine natürliche Zahl größer als 2 ist. Es gibt also keinen Drilling der Form
[mm] 7^3+8^3 [/mm] = [mm] 9^3 [/mm] usw.
Dreihundert Jahre haben fast alle Mathematiker an diesem Problem herumgeknobelt, bis es Wiles (nach 1993) gelungen ist, es zu beweisen. Diese Aussage hätte eine sein können, die innerhalb des "normalen Zahlensystems" nicht beweisbar gewesen wäre.
Noch nicht bewiesen ist z.B.:" Zwei Primzahlen, deren Differenz 2 ist, heißen Primzwillinge, z.B. 3 und 5, 5 und 7, 11 und 13, 17 und 19 usw. Behauptung: Es gibt unendlich viele Primzwillinge." Dies könnte eine Aussage sein, die durch Rechnen in unserem System der natürlichen, rationalen und reellen Zahlen nicht beweisbar ist.
Turing hat bewiesen, dass es Programme gibt, von denen nicht von vornherein festgestellt werden kann, ob sie theoretisch jemals anhalten werden oder nicht. Klar ist: Wenn ich eine Endlosschleife baue, hört das Programm nie auf (natürlich beim Ziehen des Steckers / Abbruch durch den user, aber so etwas ist nicht gemeint). Klar ist auch, dass ein Programm ohne Schleifen/Verzweigungen immer aufhört. Bei manchen Programmen erkennt man auch, dass sie bei bestimmten Eingabewerten irgendwann aufhören und bei anderen nicht. Es gibt aber Programme, da kann man erst nach dem Aufhören erkennen, dass es stehengeblieben ist, und so lange es (noch) nicht aufgehört hat, kann man nicht entscheiden, ob es das jemals tut.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:12 Fr 13.06.2008 | | Autor: | Gilga |
Danke für die Antwort.
Leider hab ich bei meiner Frage "für alle Aussagen" vergessen. Die Bedeutung von Gödels Satz ist mir bekannt.
man sollte noch erwähnen, dass Turing gezeigt hat dass es kein Programm (Turing-Maschine) gibt die für alle Turing-Maschinen entscheidet ob sie hält oder nicht.
Die Aussage von Turing ist dabei auch viel mächtiger, da nicht noch einer Begründung verlangt wird sondern die Unmöglichkeit der Existenz eines solchen Programmes bewiesen wird.
Meine Frage war eigentlich warum die wikipedia Turings Lösung des Entscheidungsproblems als Begründung für Gödelsche Unvollständigkeitssatz verwendet.
Och denke es wird eine viel schwächere Aussage bei Turing bewiesen: Ist es möglich zu entscheiden ob eine Aussage beweisbar ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:21 So 15.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
