Satz von Gödel < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:29 Mo 27.02.2006 | | Autor: | Phoney |
Hallo.
Ich habe da mal eine Verständnisfrage.
In meinem Buch steht:
Gödel erfand eine Nummernzuordnung, um zu beweisen, dass es kein aufzählbares Axiomensystem für die Theorie der natürlichen Zahlen gibt.
Mein Lehrer behauptet, Gödel hätte gesagt: Alle Probleme lassen sich auf auf Funktionen in [mm] \IN [/mm] zusammenfassen.
Ist das nicht das genaue Gegenteil und ein Widerspruch?
Oder wo wäre dann da der Unterschied?
Danke
Grüße Phoney
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:44 Mo 27.02.2006 | | Autor: | Karl_Pech |
Hallo Phoney,
Soweit ich das noch in Erinnerung habe, kann man mittels Gödelisierung jeder Turing-Maschine eine natürliche Zahl zuordnen. Hmm, und dann kann man, meine ich, auch eine Turing-Maschine konstruieren in die man dann eine solche natürliche Zahl quasi als Programm eingeben kann, wodurch diese Maschine jede andere Turing-Maschine simulieren könnte. (Hab's aber nicht mehr wirklich in Erinnerung. ![[sorry]](/images/smileys/sorry.gif "[sorry]") ) Jedenfalls wäre es dann einleuchtend, daß es kein "allmächtiges Programm" geben kann mit dem man jedes Problem lösen könnte, ohne das Programm zu verändern. Den dann gäbe es eine Turing-Maschine für dieses Programm und für diese TM gebe es eine Gödel-Nummer. Jetzt könnte man sich mal fragen, ob es eine natürliche Zahl mit einer endlichen Anzahl an Ziffern (sonst wäre es keine Zahl) geben kann, die alle Probleme der Realität erfasst. Nach Gödel ist dies wohl nicht möglich.
(Ich hoffe mal, nicht alles, was ich gerade geschrieben habe, war Unsinn.  )
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:03 Mo 27.02.2006 | | Autor: | Phoney |
Hallo Karl_Pech. Danke für deinen Zeitaufwand und verstärktes Interesse an den Fragen, die ich neuerdings so fleißig poste.
> für diese TM gebe es eine Gödel-Nummer. Jetzt könnte man
> sich mal fragen, ob es eine natürliche Zahl mit einer
> endlichen Anzahl an Ziffern (sonst wäre es keine Zahl)
> geben kann, die alle Probleme der Realität erfasst. Nach
> Gödel ist dies wohl nicht möglich.
Das klingt alles ganz logisch und verständlich. Aber nur weiss ich jetzt noch nicht zu 100%, wie ich das zu interpretieren habe:
Ist das nun falsch: Alle Probleme lassen sich auf auf Funktionen in [mm] $\IN [/mm] $ zusammenfassen.
Meiner Meinung nach ja. Aber deswegen frage ich ja...
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:34 Di 28.02.2006 | | Autor: | mathiash |
Hallo Phoney,
siehe meine Antwort zur ersten Frage Deinerseits.
Gruss,
Mathias
|
|
|
| |
|
Hallo Phoney, hallo Karl,
die behauptete ''Aussage'' Goedels, alle Probleme liessen sich auf ''Funktionen in [mm] \IN'' [/mm] zurueckfuehren,
darf man keinesfalls so interpretieren, dass alle mathem. Probleme diese Eigenschaft haben.
Sicher ist es muessig, darueber nachzudenken, was Goedel mit diesem oder einem aehnlichen Zitat genau gemeint hat,
hierzu sollte man ein Geschichtsbuch (- der Mathematik - ) konsultiern,
Wichtiger fuer jemanden, der Logik oder Rekursionstheorie oder Theor. Informatik betreibt, ist es,
das Konzept der Goedelisierung zu verstehen.
Goedel hat u.a. im wesentlichen folgendes gezeigt: Wenn man ein formales System (d.h. eine formale logische Sprache)
hat, mit nur endlich (oder abzaehlbar) vielen Axiomen, dann gibt es stets Aussagen, die man in der formalen Sprache
formulieren kann (also mathematische Aussagen), die man aber mit Hilfe der Axiome weder formal beweisen noch formal widerlegen kann.
Grundidee dabei war es, mathematische Aussagen durch natueliche Zahlen zu codieren und somit selber wieder zu Objekten mathematischer Aussagen zu machen.
Solche Codierungen von mathematischen Aussagen (d.h. zB praedikatenlogischen Formeln erster Stufe) oder auch
in leicht anderem Kontext von Turing-Maschinen oder aehnlichem durch natuerliche Zahlen nennt man dann auch im
allgemeinen Goedelisierungen.
Ich wage einen kleinen Exkurs, um zu verdeutlichen, wie das Konzept funktioniert, und zwar einen Exkurs in die
Rekursionstheorie.
Lest vorbereitend die Begriffe Berechenbarkeit (Rek. Aufzaehlbarkeit) und Entscheidbarkeit (Rekursivitaet) nach.
Dann sei eine Codierung
[mm] c\colon\: \{M\:\: |\:\: M\: ist\: eine\: Turing-Maschine\}\:\to\:\IN
[/mm]
gegeben, eine Goedelisierung, d.h. so, dass es eine Universelle Turing-Maschine gibt, also eine TM U mit
der Eigenschaft, dass U bei Eingabe c(M), x die Maschine M auf Eingabe x simuliert, ich erlaube mir zu schreiben:
U(c(M),x)=M(x).
Nun ist es aus Kardinalitaetsgruenden klar, dass es Sprachen [mm] L\subseteq\{0,1\}^{\star} [/mm] gibt, die weder rekursiv noch
rekursiv aufzaehlbar sind (Warum ?)
Aber man kann - und das geht nicht mit einem Kardinalitaetsargument- zeigen: Es gibt Sprachen, die rekursiv aufzaehlbar, aber nicht rekursiv sind.
Beispiel: Das Halteproblem
[mm] K=\{c(M)\: |\:\:\ M\:\: Turing-Maschine,\:\: M\: auf\: Eingabe\: c(M)\: haelt\}
[/mm]
(1) K ist rek. aufzaehlbar.
(2) Annahme: K rekursiv.
Dann gaebe es eine TM [mm] M_0, [/mm] so dass fuer alle TM M gilt:
[mm] M_0(c(M))=\begin{cases} 1, & M(c(M)) haelt\\ 0 & sonst \end{cases}
[/mm]
Dann gibt es aber auch eine TM [mm] M_1, [/mm] die sich wie folgt verhaelt:
[mm] M_1(c(M))=\begin{cases} 1,& M(c(M)) haelt nicht\\ ''Endlosschleife'' & sonst\end{cases}
[/mm]
Nun betrachtet die beiden Faelle:
(1) [mm] c(M_1)\in [/mm] K
(2) [mm] c(M_1)\not\in [/mm] K
Beide fuehren zum Widerspruch (warum ? Definitionen einsetzen, steht alles hier !!!),
also kann solches [mm] M_0 [/mm] nicht existieren.
Vorest viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:39 Di 28.02.2006 | | Autor: | Phoney |
Hi.
Danke für deine Erklärung.
> Sicher ist es muessig, darueber nachzudenken, was Goedel
> mit diesem oder einem aehnlichen Zitat genau gemeint hat,
> hierzu sollte man ein Geschichtsbuch (- der Mathematik - )
> konsultiern,
Danke, dass du es gemacht hast und eine so umfassende Antwort geschrieben hast.
> Beispiel: Das Halteproblem
>
> [mm]K=\{c(M)\: |\:\:\ M\:\: Turing-Maschine,\:\: M\: auf\: Eingabe\: c(M)\: haelt\}[/mm]
>
> (1) K ist rek. aufzaehlbar.
>
> (2) Annahme: K rekursiv.
>
> Dann gaebe es eine TM [mm]M_0,[/mm] so dass fuer alle TM M gilt:
>
> [mm]M_0(c(M))=\begin{cases} 1, & M(c(M)) haelt\\ 0 & sonst \end{cases}[/mm]
>
> Dann gibt es aber auch eine TM [mm]M_1,[/mm] die sich wie folgt
> verhaelt:
>
> [mm]M_1(c(M))=\begin{cases} 1,& M(c(M)) haelt nicht\\ ''Endlosschleife'' & sonst\end{cases}[/mm]
>
> Nun betrachtet die beiden Faelle:
>
> (1) [mm]c(M_1)\in[/mm] K
>
> (2) [mm]c(M_1)\not\in[/mm] K
>
Ich studiere weder Mathe noch Informatik. Daher wird mein Wissen leicht irgendwo abgehangen. Aber genau das habe ich HEUTE auch in einem Buch gelesen. Naja, nicht das gleiche, aber es lief auf das selbe heraus. Von wegen Mengen der Rationalen und natürlichen Zahlen etc.
Vielen Dank!
Gruß
|
|
|
|
