Prinzipielle Grenzen der Berechenbarkeit: Unterschied zwischen den Versionen
(→Gödelisierung) |
K (→Gödelisierung) |
||
| Zeile 95: | Zeile 95: | ||
| − | Mit der Gödelisierung lassen sich beliebige | + | Mit der Gödelisierung lassen sich beliebige Ein- und Ausgaben in natürliche Zahlen umwandeln und umgekehrt. Diese Vorgehensweise wird häufig in der theoretischen Informatik verwendet, da sich Algorithmen dadurch als Funktionen über den natürlichen Zahlen abbilden lassen. Zur Umwandlung gibt es verschiedenste Verfahren. |
{{Definition| | {{Definition| | ||
| − | Eine '''Gödelisierung''' ist eine Abbildung <math>g</math> von der Menge der | + | Eine '''Gödelisierung''' ist eine Abbildung <math>g</math> von der Menge der Ein- und Ausgaben <math>M</math> eines Algorithmus in die Menge der natürlichen Zahlen <math>\mathbb{N}</math>: <math>g: M \rightarrow \mathbb{N}</math>. |
Die Abbildung muss dabei noch drei Bedingungen erfüllen: | Die Abbildung muss dabei noch drei Bedingungen erfüllen: | ||
| Zeile 104: | Zeile 104: | ||
* Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt. | * Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt. | ||
* Die Umkehrfunktion <math>g^{-1}</math> muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können. | * Die Umkehrfunktion <math>g^{-1}</math> muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können. | ||
| + | [[Bild:HaeufgloecknerGödelisierung.png|frame|Funktionsweise der Gödelisierung]] | ||
}} | }} | ||
Version vom 25. September 2009, 14:44 Uhr
Inhaltsverzeichnis |
Algorithmus
Definition
Ein Algorithmus ist eine Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, die aus endlich vielen Eingabedaten endlich viele Ausgabedaten erzeugt und mit der man eine Vielzahl gleichartiger Aufgaben lösen kann.
Wie du sicher bemerkt hast, kommt in dieser Definition sehr oft der Begriff "endlich" vor. Dies wird später noch eine entscheidende Rolle spielen!
Wobei handelt es sich um einen Algorithmus? (Lösen einer quadratischen Gleichung) (!Auflistung aller Primzahlen) (Konstruieren eines Kreises durch 3 Punkte, die nicht auf einer Gerade liegen) (Wechseln eines Autoreifens) (!Schreiben einer Eins in der Schulaufgabe)
Gödelisierung
Wir versuchen jetzt Hilfe von der Mathematik zu erhalten. Dazu wandelt man Probleme in eine Form um, die es erlaubt, Wissen über Abbildungen innerhalb der natürlichen Zahlen zu benutzen. Um dies zu erreichen, wandelt man die Ein- und Ausgabedaten in natürliche Zahlen um. Dies kann mehr oder minder geschickt erfolgen. Kurt Gödel hat sich mit solchen Fragestellungen beschäftigt, weshalb man entsprechende Verfahren Gödelisierungen nennt..
Aufgabe
Die 26 Buchstaben des Alphabets werden mit den Zahlen 1 bis 26 kodiert. Damit könnte man ein geschriebenes Wort als Zahl schreiben. Dekodiere die Zahl "26235945212097"! Welche Buchstabenfolge erhält man nach dem Dekodieren?
Möglichkeiten für das dekodierte Wort sind z.B.: ZWEIDEUTIG oder BFBCEIDEBATIG oder ...
|
Aufgabe
Nun werden die 26 Buchstaben des Alphabets wie folgt kodiert: Den 26 Buchstaben des Alphabets wird jeweils eine eindeutige Zahl zwischen 1 und 26 zugeordnet. Ein Wort wird nun mit fortlaufenden Primzahlpotenzen kodiert, also wenn a die Zahl 1, b die Zahl 2, c die Zahl 3 zugeordnet wird, dann wird das Wort abbca wie folgt kodiert:
Multipliziert man diese Zahlen miteinander, erhält man die Zahl
Das dekodierte Wort lautet: INFORMATIK. Dies Art der Kodierung ist eher von theoretischer Bedeutung, weil man sehr schnell gigantisch große Zahlen erhält. Es ist auch ziemlich aufwändig diese Zahlen in Primfaktoren zu zerlegen. Aus diesem Grund sind große Primzahlen für die Verschlüsselungstechnik so wichtig.
|
kodiert.
kodiert.
kodiert.
kodiert.
kodiert.
.
Da die Primfaktorzerlegung eindeutig ist, wenn man die Primzahlpotenzen aufsteigend ordnet, kann man aus jeder Zahl das zugehörige Wort erzeugen.
Welche Buchstabenfolge erhält man, wenn man die Zahl 
dekodiert?
Aufgabe
Nun werden die 26 Buchstaben des Alphabets mit den Zahlen 01 bis 26 kodiert. Schreibt man die kodierten Buchstaben hintereinander, so erhält man eine Zahl. Dekodiere die Zahl 26230509060512121519.
Das dekodierte Wort lautet: ZWEIFELLOS
|
Mit der Gödelisierung lassen sich beliebige Ein- und Ausgaben in natürliche Zahlen umwandeln und umgekehrt. Diese Vorgehensweise wird häufig in der theoretischen Informatik verwendet, da sich Algorithmen dadurch als Funktionen über den natürlichen Zahlen abbilden lassen. Zur Umwandlung gibt es verschiedenste Verfahren.
Definition
Eine Gödelisierung ist eine Abbildung 
von der Menge der Ein- und Ausgaben 
eines Algorithmus in die Menge der natürlichen Zahlen 
: 
.
Die Abbildung muss dabei noch drei Bedingungen erfüllen:
- muss injektiv sein, d.h. jede natürliche Zahl darf höchstens das Bild von einem Programm sein; aber nicht jede natürliche Zahl muss auch ein Programm sein
- Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt.
- Die Umkehrfunktion
muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können.
Welches der obigen Verfahren eignet sich für eine Gödelisierung? (!Kodierung mit Zahlen 1 bis 26) (Kodierung mit Zahlen 01 bis 26) (Kodierung mit Primzahlpotenzen)(!Keines der Verfahren)
Entscheidbarkeit
Berechenbarkeit
Fleißige Biber
Halte-Problem
Aufgabe
Die Schüler der Kollegstufe besuchen |
verschiedene Kurse. Jeder Kurs findet einmal pro Woche statt. Belegt ein Schüler zwei Kurse, so dürfen diese nicht gleichzeitig stattfinden. Kann man mit 
verschiedenen Terminen auskommen?
Erstelle hierzu eine Graphen, wobei ein Knoten einem Kurs entspricht. Zwei Knoten werden genau dann miteinander verbunden, wenn ein Schüler die beiden entsprechenden Kurse besucht.
Man kann die Aufgabe als sogenanntes 
