+ All Categories
Home > Documents > Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Date post: 05-Apr-2015
Category:
Upload: christianne-woerner
View: 112 times
Download: 1 times
Share this document with a friend
48
Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE
Transcript
Page 1: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Eine sehr kurze Geschichte der(theoretischen) Informatik

Prof. Dr. Wolfram Conen, FH GE

Page 2: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Ziele der Vorlesung

Theoretische Informatik kurzgefaßt: Lernen sie einige Personen und Resultate kennen, die sie kennen sollten

Nebenbei zeigen, dass damit viele spannende Fragen verbunden sind!

... und einige dieser Fragen sollten Sie nach der Vorlesung bzw. nach dem Durcharbeiten der Vorlesung auch beantworten können!

Page 3: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Wichtige Fragen eines Informatikers

(F1) Wie lassen sich mein Problem und eine ev. Lösung präzise beschreiben?

(F2) Ist das Problem überhaupt lösbar?

(F3) Wenn ja, kann ich es auch mit vertretbarem Aufwand lösen?

(F4) Wie kann ich das Problem lösen?

Page 4: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Hilberts Suche nach Wahrheit

„Da ist das Problem, suche die Lösung. Du kannst sie durch reines Denken finden; denn in der Mathematik gibt es keinen

Ignorabimus*!“, David Hilbert (1862-1943), 1900,(*ignorabimus: wir werden nicht wissen,

lat.)

Dass die Mathematik das wirklich kann, war noch nicht „bewiesen“!

Zwei Dinge waren vor allem zu erledigen:

1. Eine „Sprache“ finden, um Probleme und deren Lösung präzise beschreiben zu können.

2. Ein „durchführbares“ Verfahren finden, um in endlichen vielen Schritten die Lösung auch tatsächlich bestimmen zu können.

Page 5: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Logik als Schritt zur Lösung... Präzision ist eine wesentlich Voraussetzung für Analyse und

Lösung von Problemen (F1)

Logikformalismen helfen, Probleme und Lösungen formal präzise zu beschreiben

Am weitesten vorgedrungen war Gottlob Frege mit seiner „Begriffsschrift“.

1902 sollte Band II seines großen Werks zur Fundierung der Arithmetik (und damit der Mathematik) mit Hilfe der Logik erscheinen.

Aber dann erhielt Frege einen Brief...

Page 6: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Ein Brief von Bertrand RussellBitte, lösen Sie das folgende Problem:

Sie arbeiten in dem Semesterferien in der Bibliothek der FH. Jedes Buch muß in zwei sehr großen Katalogen erfaßt werden. Der Katalog A enthält eine Referenz auf jedes Buch,

das sich nicht selbst referenziert. Katalog B enthält eine Referenz auf jedes Buch,

das sich selbst referenziert. Eine älterer Bibliothekar fragt Sie nun zunächst:

„In welchem der beiden Kataloge sollte der Katalog B erfaßt werden?“ Als aufmerksamer Mitarbeiter schlagen Sie Katalog A vor, da B sich nicht

selbst referenziert. Darauf folgt die Frage, wo Katalog A zu erfassen ist. Ihre Antwort?

Dieses Paradox läßt sich auch in die logisch-mathematische Sprache Freges (im Grunde Prädikatenlogik mit All- und Existenzquantor) übersetzen: R ist die Menge, die alle Mengen enthält, die sich nicht selbst enthalten. Gehört R sich selbst an?

Nicht jedes präzise formulierbare Problem hat auch eine „sinnvolle“ Lösung!

Page 7: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Freges Scheitern

„Einem wissenschaftlichen Schriftsteller kann kaum etwas Unerwünschteres begegnen, als dass ihm nach Vollendung einer Arbeit eine der Grundlagen seines Baues erschüttert wird. In diese Lage wurde ich durch einen Brief des Herrn Bertrand Russell versetzt, als der Druck dieses Bandes sich seinem Ende näherte“

[Gottlob Frege, Grundgesetze der Arithmetik, Band II, Nachwort, Jena, im Oktober 1902]

Page 8: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Freges Begriffsschrift

„Man findet in diesem Buche Lehrsätze, auf denen die Arithmetik beruht, mit Zeichen bewiesen, deren Ganzes ich Begriffsschrift nenne.“

(Frege in Band I zu der Grundgesetze)

Page 9: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

... und Hilberts „Programm“? Hilbert hat diese Paradox zunächst nicht sehr ernst genommen!

(Frege schon...) Russell selbst hat 1912 in „Principia Mathematica“ (mit

Whitehead) einen Formalismus vorgeschlagen, der solche Paradoxien vermeiden sollte (durch Typisierung und das Verbot, dass ein Typ über sich selbst spricht).

Noch 1930 sagt Hilbert auf einem Kongreß in Königsberg: „es gibt kein unlösbares Problem...“ und formuliert die berühmten und auf seinem Grabstein verewigten Sätze:

Wir müssen wissen. Wir werden wissen.

Zu dieser Zeit erfährt John von Neumann (damals Assistent von Hilbert in Göttingen) von einem Resultat eines jungen Österreichers... (von Neumann hat danach nichts mehr zu Logik veröffentlicht)

Page 10: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Kurt Gödel

28. April 1906, Brünn 1931: Über formal

unentscheidbare Sätze der Principia Mathematica (in jedem hinreichend mächtigen Axiomensystem (z.B. natürliche Zahlen / Arithmetik) lassen sich wahre Aussagen formulieren, deren Wahrheit nicht innerhalb des Systems bewiesen werden kann).

14. Januar 1978 Tod in Princeton durch Selbstaushungern.

Page 11: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Hilberts Enttäuschungen

Der Beweis funktionierte mittels einer Paradoxie, die in die Russel‘sche Logiksprache über die Arithmetik eingeschmuggelt wird!

Ein ähnlich unglückliches Schicksal stand Hilberts Suche nach einem Lösungsverfahren bevor...

...ein Amerikaner (Alonso Church) und ein junger Engländer nahmen sich des Problems an. Und wieder spielt eine Paradoxie eine wichtige Rolle.

Page 12: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Alan Turing

23. Juni 1912, London 1936: On computable

numbers with an application to the Entscheidungs-problem (es gibt keine „definite“ Methode, die für jede mathematisch-logische Aussage entscheiden kann, ob sie beweisbar ist oder nicht.)

1939-40: Entwicklung der Bombe (zur Entschlüsselung der deutschen Enigma-Codes)

7. Juni 1954: Selbstmord

Page 13: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Von der Intuition zur Exaktheit Hilbert suchte nach einem Verfahren, das für jede mathematisch-

logische Aussage einen Beweis oder eine Widerlegung liefert:

„Das Entscheidungsproblem ist gelöst, wenn man ein Verfahren kennt, das bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen die Entscheidung über die Allgemeingültigkeit bzw. Erfüllbarkeit erlaubt. (...) Das Entscheidungsproblem muss als das Hauptproblem der mathematischen Logik bezeichnet werden“,

Hilbert, Ackermann, Grundzüge der theoretischen Logik, 1928

Um zu zeigen, dass es so ein Verfahren gibt, könnte man einfach eines angeben.

Turing wollte zeigen, das es ein solches Verfahren nicht geben kann!

Er mußte etwas finden, dass Hilberts Intuition eines Verfahrens entsprach, diese präzisierte und wesentliche Eigenschaften aller anderen „möglichen“ Verfahren beinhaltete und so als „Prototyp“ dienen konnte:

Wenn der Prototyp die gewünschte Antwort nicht geben kann, dann kann es auch kein anderes Verfahren!

Page 14: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Die Turing-Maschine: Ein Modell der Berechenbarkeit

...... 0 0 0 1000

Zustand: z1

„Programm“

Falls Zustand == z1 und Zeichen unter Schreib/Lesekopf == 0,

dann schreibe 1, gehe in den Zustand z1 und bewege dich ein Feld nach rechts.

Kurz: (z1,0) (1,z1,R) (z1,1) (0,z1,R) (z1,_) (_,ende,L)

Was macht dieses Programm?

Page 15: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Die Turing-Maschine: Eine Berechnung

...... 0 0 0 1001

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

0

Page 16: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 1111

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

1

Page 17: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 0 0111

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

Page 18: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 0111

Zustand: ende

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

0

Die Berechnung hält an! (Man sage: Sie terminiert)

Noch wichtig: Programm, Eingabe und Zeichensatz sind endlich, das Band aber nicht.

Page 19: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Universelle TM (1)

Turing führt eine Turing-Maschine UTM ein, die andere Turingmaschinen simulieren kann Bisher:

Eingabestring x ! Turingmaschine TM ! Ausgabestring y;kurz: TM(x) = y

Jetzt: Kodieren des Anweisungen der Turingmaschine als String z Eingabestring zx ! Turingmaschine UTM simuliert TM und

wendet die Simulation auf x an ! Ausgabe y;kurz also: UTM(zx) = y bzw. UTM(TM,x) = y

Die UTM von Turing kann alle Turingmaschinen simulieren...sie ist in einem bestimmten Sinn universell

Page 20: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Universelle TM (2)

B0.UTM=1000000101110100000001010110100000010010110100001010110100000100010110101001110100000101010111010000111010000100101011101001001101000010100101101010001101000100010101101010100111010010101010010111010000011101000000000111010000001010110100000100101101001000110100010101001011010010001000110100101010001110101000011101001010010010111010010001001011010100010100111010010000001110101010010111010010010100111010101010101110100000011101001010101010111010000100110100011010001010000110100000101110101001010001011101000101010111010010000110101010010100101101010010110100100101011010100010101101001010010111010101000010011101001010101011101000101010011101010000101101010010001101010001010110100010000101110101001011010010010011010100101010110100100100010111010101000101110101010100011010101001010110100100010110101010100101100111010001001011101001000001110100010001011101001000110100000101011010010010010011101000010010110100100110100001010101101010010010111010011010000000111010001001010110100100010101110100010100101110101001000101110100100001011101001010001010111010100100010111010010010010111010010100010111010010010001110100101000011101000100011010010100100111010010001001110100001110100101001110101001001110100101001110100101010111010000001110101000100010111010100010100101110101000001011101001000001110101000010101101000100110101000100101110101001001110101001010111010010101001010111010100010010101110101010100010111010100100101011101000010101101010100010101100111010101010101001011010001010110101010000101110101010010010110101000000111010001000001110100010001110100001110101010100101011101010000010011101001010000011101000011101010100101110100100000101110100000000110100100110100001010101011010100000010110100001010101101000100110100001000011010001010110100000100110101001110100000010101011101001011010000100010110100001110101010010101011101001001101010101010101011010010011010001001010110100100101011101010101110101000110101010001010101101010000100101101010100101110100000001110100010100101011010010000100111010001010001011010000000111010001010010111010010001101000101010101011010010001101001000101010110100010000110101010101000111010101010100100111010010000100111010000001001101000001000110100100011010000100101101000101011101010010010011101010000011101011101010101010101010110100100101010101101010000100110100010100111010101010000111010101010100001110100001001011101010001011101010000111010010100101010111010100001110100101010001011101010000111010100010010111010001000101110101010101110101010011101001010101010101110101010011101010000101010111010000000011010000000101101010000100011010100000001101000100100011010001001001011010101001110101010000101110100000011101010010000101110101000000111010100100101010111010001101010001010101011101000110101001000101011101000000111010101000001011101000110101001001001011101000110101010101011101000101001110101001110100110101001010010101110100110101001010100101110100110101001010101010111010011010010101010111010010100011101001001101000100101101010100010010111010101001001101010010100110101000110101010010001011010100011010101001001010110100001011101010010101010110100100001101010100101010101101001000011010101010000101101001000011010000000001110100001011101010101001001011101000010111010101010010101011101000010111010010010001011101010000010101110100101000010111011011100111010100001011001110101010101010110100001011101010101000101011101000001010110101011010001001010101101001001010010110101001110100000100101011101000010101101010010100101101010011101000001010010111010101000101110100001

Eine „binäre“ UTM von Stephen V. Gunhouse mit 176 Zuständen

Page 21: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Was kann die Turing-Maschine? „Alles Machbare!“

Genauer formuliert dies die Church-Turing-These:„Genau das, was wir intuitiv für „effektiv berechenbar“ halten, kann

durch die Turing-Maschine tatsächlich berechnet werden.“

Wir nennen ab jetzt etwas berechenbar, wenn es eine Turingmaschine gibt (geben kann), die mit dem richtigen Ergebnis anhält!

Es wurden noch viele andere Modelle der Berechenbarkeit „erfunden“ (generelle rekursive Funktionen, -Definierbarkeit, Kombinatorische Systeme, Termersetzungssysteme, Registermaschinen, ...), aber alle (zumindest alle physikalisch realisierbaren) erwiesen sich als

„äquivalent“, sie können die gleichen Probleme lösen! Zeigen kann man dies, in dem man ein Modell durch ein anderes simuliert

(und vice versa).

Merke: Modelle der Berechenbarkeit präzisieren den Begriff Algorithmus / Lösungsverfahren (F1)

Page 22: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Das Halteproblem

Hält eine gegebene TM für eine gegebene Eingabe? Gesucht ist eine „Prüfmaschine“ P(A,x), die ein Programm A und

eine Eingabe x erhält und die Frage nach der Terminierung von A(x) mit JA oder NEIN beantwortet:

P(A,x) = JA, falls A(x) anhält.

P(A,x) = NEIN, falls A(x) nicht anhält. Angenommen, es gäbe eine solche Maschine P! Dann bauen wir eine Maschine G(A), die P verwendet:

G(A) Endlosschleife, falls P(A,A) = = JA

G(A) Hält an, falls P(A,A) = = NEIN Nun rufen wir G(G) auf! Voilà! Ein weiteres Paradox!

Page 23: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Emil Post und die Dominos

Emil Post, geb. in Polen, 1897-1954

Veröffentlicht 1936 sein Paper über endliche kombinatorische Prozesse (äquivalent zu Turingmaschinen)

Formuliert ein berühmtes nicht-berechenbares Problem, das Post‘sche Korrespondenzproblem

Page 24: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Post‘sches Korrespondenzproblem (1) Gegeben sind drei Typen von „flexiblen“ Dominosteinen: (Ober- und Unterteil sind durch ein Gummiband verbunden)

Es gibt jeweils beliebig viele von solchen Dominos!

101

1

10

00

11

011

101

1

10

00

10

00

11

011 Gesucht ist eine Folge vonDominos, so dass die Zeichen oben und unten an jeder Position übereinstimmen (die Gummibänder dürfen sich natürlich nicht überschneiden und die Dominoteile müssen bündig liegen!

101

1

11

01110

00

Page 25: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Post‘sches Korrespondenzproblem (2)

11

01110

00

3 Typen sind gegeben.

101

1

11

011

101

1

11

01110

00

Lösungssequenz aus 4 Steinen

Page 26: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Post‘sches Korrespondenzproblem (3)

4 Typen sind gegeben.001

0

01

011

01

101

10

001

Hat dieses PCP (Post correspondence problem) eine Lösung?

Ja, aber ein lange...versuchen sie es mal...es braucht min. 66 Dominos!

01

011

01

101

10

001

10

001

10

001

01

011

001

0

01

011

Page 27: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

PCP formal

Wir haben ein endliches Alphabet V zur Beschriftung der Dominos, z.b. V = {0,1}

Und k vorgegebene Dominotypen der Form (xi,yi), 1 · i · k. Hierbei sind xi und yi jeweils nichtleere Wörter über dem Alphabet, also xi, yi 2 V+, z.B. xi = 001, yi = 10

Gesucht ist eine Folge von Dominos (i1,i2,...,in) mit ij 2 {1,...,k}, so dass gilt

xi1xi2

...xin = yi1

yi2...yin

Page 28: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Sind alle PCPs lösbar?

Natürlich gibt es unlösbare PCPs:

Man kann die Lösung lösbarer PCPs durch ausprobieren sicher nach endlich vielen (vielen) Schritten finden: Breitensuche im Baum der möglichen Lösungen

An der ersten Stelle steht ein Domino eines der k Typen (also ein Entscheidungsknoten mit k Kindern)

An der zweiten Stelle wieder ein Domino eines der k Typen (also Verzweigungsfaktor immer k)

1

0

Page 29: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Sind alle PCPs lösbar? Wenn man es auf diese Art der Aufzählung (Enumeration) der

potentiellen Lösungswege probiert, dann kommt man natürlich bei einem unlösbaren PCP nie zu einem Ende!

Auf diese naive Art kann man also nicht entscheiden, ob ein PCP lösbar ist oder nicht, denn wenn man nach langer Zeit noch keine Lösung gefunden hat (Fall 1) dann gibt es keine! ... oder ... (Fall 2) man hat noch nicht lange genug gesucht!

Unangenehmerweise kann man zeigen, dass man auch durch Analyse der Problemstellung unlösbare Probleme nicht immer erkennen kann (beim unlösbaren Beispielproblem geht das natürlich leicht, weil unten andere Zeichen vorkommen, als oben)

Page 30: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Sind alle PCPs lösbar?

Deshalb nennt man das PCP auch „semi-entscheidbar“:

Man kann einen (einfachen) Algorithmus (in Form einer Turingmaschine, z.B.) angeben, der lösbare Instanzen der Problems sicher erkennt und eine Lösung findet

Allerdings kann er unlösbare Instanzen nicht sicher in endlicher Zeit erkennen – und es kann keinen Algorithmus geben, der das könnte (sonst wäre das Halteproblem lösbar...so ist meist die Standard“reduktion“)

Page 31: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Entscheidbarkeit

Eine JA-NEIN-Fragestellung ist dann entscheidbar, wenn jede Instanz dieser Fragestellung (also jede Frage dieses Typs) durch einen Algorithmus (also eine Turingmaschine) korrekt und sicher in endlicher Zeit mit JA oder NEIN beantwortet wird.

Die Fragestellung ist semi-entscheidbar, wenn ein Algorithmus existiert, der für JA-Instanzen sicher in endlicher Zeit mit JA antwortet (und NEIN-Instanzen nicht mit JA beantwortet – diesen Aspekt kann man aber aufweichen)

Page 32: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Entscheidbarkeit

Die klassische Fragestellung in der Mathematik ist die folgende: Gegeben sei die Beschreibung einer Menge M Ist ein gegebenes Objekt x Element dieser Menge?

Übertragen in die Informatik: Gegeben sei die Beschreibung einer Sprache L Ist ein gegebenes Wort x Element dieser Sprache?

Beide Fragen stellt man in der Regel mit Bezug zu einer Grundmenge, aus der x stammt bei den Mengen ist es ein (Diskurs-)Universum U bei den Sprachen die Menge aller Wörter V* über einem

Alphabet V

Page 33: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Entscheidbarkeit (in der Informatik) Gegeben sei ein Alphabet V, z.B. {0,1}

Gegeben sei die Beschreibung einer Sprache L, z.B. L = {0n1n}

Ist ein gegebenes Wort x 2 V* Element dieser Sprache, z.B. x = 000111? V* ist die Menge aller mit Zeichen aus V bildbaren Wörter

inklusive des leeren Wortes V+ ist die Menge aller nichtleeren Wörter, die sich mit Zeichen

aus V bilden lassen Die Sprache zur Beschreibung der Mengen haben wir noch nicht

präzisiert, aber 0n bedeutet z.B. n hintereinander geschriebene Nullen

Page 34: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Entscheidbarkeit in der Informatik Die Frage nach der Entscheidbarkeit ist ziemlich

universell: Ist n eine Primzahl? Ist T ein Spannbaum für G? Ist x eine Lösung mit Weglänge y für ein TSP z?

Sie „implementiert“ Boole‘schen Funktionen: f: U ! {true,false}, f(x) = ? für x 2 U, f bestimmt eine Menge

X und eine Menge X‘ (Komplement zu X in U) mit X [ X‘ = U f(x) = true für alle x 2 X f(x) = false für alle x 2 X‘

Page 35: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Berechenbarkeit

Allgemeiner kann man auch nach bel. Funktionswerten fragen: Sei f: N ! N durch eine Beschreibung gegeben Bestimme y=f(x) für gegebene x 2 N

Eine solche Funktion f heißt berechenbar, wenn es einen Algorithmus (also eine Turingmaschine) gibt, die für jedes x 2 N sicher in endlicher Zeit den Funktionswert y=f(x) bestimmt

Page 36: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Noch ein Beispiel...fleissige Bieber Bieber bauen Dämme aus Baumstämmen... Als Turingmaschine sieht das z.B. so aus:

z1 z2 z3 halt

1/1,L _/1,L

_/1,R 1/1,R

1/1,R_/1,L

_ _ _ _ _ _ _ _ _ _ _

z1 z2z1z1 z2z1 z3

1 111

z2 z3

11 1

z2z1z1 z2z1 z2z1 z3 haltz3

_/1,R

_/1,L

_/1,R

_/1,L1/1,L1/1,L

_/1,L_/1,L

_/1,L_/1,L

_/1,R_/1,R 1/1,R1/1,R

_/1,L_/1,L1/1,L1/1,L

1/1,R1/1,R

Page 37: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Noch ein Beispiel...fleissige Bieber Ein Bieber ist eine deterministische Turingmaschine mit

Mit dem Bandalphabet V = {1} und dem Blanksymbol _ mit einem in beide Richtungen unendlichen Band das Band ist zu Beginn leer (also voller Blanks) die Maschine muß sich bei jeder Anweisung bewegen - entweder

nach links (L) oder rechts (R) sie hat einen Endzustand, der keine Ausgänge hat sie muß diesen Endzustand erreichen sie hat n weitere Zustände, die keine Endzustände sind, einer

davon ist der Startzustand Einen solchen Bieber wollen wir auch n-Bieber nennen

Deterministisch heißt: ich weiß immer, welche Anweisung als nächste dran ist, d.h. die Überführungsrelation ist eine Funktion

Page 38: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Noch ein Beispiel...fleissige Bieber Ein fleißiger Bieber ist ein n-Bieber, der

mindestens soviele Einsen erzeugt, wie jeder andere n-Bieber

Unser Beispiel ist ein fleißiger 3-Bieber Die Rado-Funktion Rado(n) gibt für n an, wieviele

Einsen ein fleißiger n-Bieber erzeugt Rado(3) = 6 (s. Beispiel) PS: die Einsen können auch blanks zwischen sich haben

Diese „Busy Beavers“ sind sehr schwer zu finden!

Page 39: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum? Erstens...

Der Suchraum wird schnell extrem groß:(4(n+1))2n verschiedene Turingmaschinen für n Zustände für jeden Nicht-Endzustand gibt es zwei

Ausgänge, also 2n Transitionen (=Zustandsübergänge)

Jede Transition kann 1 oder _ schreiben (2) sich nach links oder rechts bewegen (2*2) zu einem von n+1 Zuständen führen (2*2*(n+1))

Insgesamt also (2*2*(n+1))2n

Page 40: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum? Zweitens... Da das Halteproblem nicht

allgemein lösbar ist, könnte es schwierig werden, nicht-haltende Lösungskandidaten zu erkennen...auch kleine Bieber können nämlich schon ganz schön lange arbeiten z.B. ist Rado(8) ¸ 1044 ... oops!

Wir werden gleich zeigen, dass es tatsächlich unmöglich ist, Rado(n) für beliebige n zu berechnen

Allerdings kann man mit brutaler Gewalt zumindest für manche kleine n Rado(n) bestimmen oder abschätzen:

n Rado(n) Quelle

1 1 Lin/Rado

2 4 Lin/Rado

3 6 Lin/Rado

4 13 Brady

5 ¸ ¸ 4098 Marxen/Buntrock

6 ¸ 95.524.079 Marxen

Page 41: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum? Zweitens...

Ein 6-Bieber, der 95.524.079 Einsen erzeugt und dann hält (gefunden von Heiner Marxen 1996/97) – vielleicht ist der Bieber auch fleißig?!

Page 42: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum sind fleißige Bieber unberechenbar? Satz: Die Rado-Funktion kann nicht durch eine Turing-

Maschine berechnet werden Beweisidee: Sei f eine beliebige berechenbare Funktion von N

nach N, dann existiert ein n0, so dass Rado(n) ¸ f(n) für n ¸ n0 (d.h. die Rado-Funktion wächst schneller, als jede berechenbare Funktion)

Beweis: Ohne Beschränkung der Allgemeinheit ist unsere berechenbare

Funktion f durch ein Turingmaschine TM mit den folgenden Eigenschaften implementiert: Auf dem Band steht ein Block von n Einsen direkt rechts von einem

Blank, auf dem der Lesekopf zu Beginn steht TM hält nach einer endlich vielen Schritten und hinterläßt einen

Block von f(n) Einsen auf dem Band

Page 43: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum sind fleißige Bieber unberechenbar? Zu unserem beliebigen berechenbaren f läßt sich die folgende

Funktion F angeben:

F(x) = 0 · 1 · x (f(i) + i2)

Weil f berechenbar ist, ist auch F berechenbar (denn f und alle andere Operationen, also Quadrieren, Addieren und Summieren sind berechenbar)...

...und es existiert eine Turingmaschine TMF, die mit einer Eingabe eines Blocks von x Einsen einen Block von F(x) Einsen rechts neben den Eingabeblock schreibt (getrennt durch mindestens ein Blank)

Wir nehmen an, dass TMF n Zustände hat

Page 44: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum sind fleißige Bieber unberechenbar? Wir konstruieren nun eine Turingmaschine M

sie beginnt auf einem leeren Band schreibt x Einsen hält mit dem Lesekopf auf der letzen Eins rechts Dies kann für jedes x mit x Zuständen realisiert werden

Dann benutzt M TMF und schreibt rechts, durch mindestens ein Blank getrennt, F(x) auf‘s Band

Dann wird nochmals TMF benutzt, um rechts, wieder durch mindestens ein Blank getrennt, F(F(x)) auf‘s Band zu schreiben

M hat also x + 2*n Zustände

Page 45: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Warum sind fleißige Bieber unberechenbar? Aus der Definition des fleißigen Biebers folgt, dass der (x+2n)-Bieber

mindestens so viel Einsen auf‘s Band schreibt, wie M, d.h.:

Rado(x+2n) ¸ x + F(x) + F(F(x)) Allerdings...

F(x) ¸ x2 [klar, denn F(x) = 0 · 1 · x (f(i) + i2)] Und es existiert eine Konstante c1 mit x2 > x+2n für alle x ¸ c11 [klar, n ist ja

konstant] Also gilt: F(x) > x +2n für x ¸ c1

Auf der Definition von F folgt außerdem F(x) > F(y) für x > y, also F(F(x)) > F(x+2n) für x ¸ c1.

Also Rado(x+2n) ¸ x+F(x)+F(F(x)) > F(F(x)) > F(x + 2n) ¸ f(x+2n) für x ¸ c1, d.h. Rado ist ab c11 größer als f

Da f beliebig gewählt war, kann die Rado-Funktion nicht berechenbar sein, sonst könnten wir sie für f einsetzen und hätten dann gezeigt, dass ab einem sicher existierenden c1 Rado(x) > Rado(x) ist, ein Widerspruch! [Malen Sie sich ein Bild zur Verdeutlichung!]

Page 46: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Luftholen...

Wahre Titanen des Geistes (auch, wenn manche von Ihnen ein unglückliches Ende gefunden haben...) legten die Grundlagen.

Wir wissen jetzt: es gibt Probleme, die sich nicht lösen lassen, obwohl sie „mathematisch genau“ beschrieben sind!

Modelle der Berechenbarkeit erlauben eine Analyse der Berechenbarkeit/Lösbarkeit eines Problems! (F2)

Aber: wie schwer kann es werden, ein konkretes Problem tatsächlich zu lösen? [Das ist Thema des zweiten Teils]

Page 47: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Verständnisfragen (Klausurrelevant!) Ist die Rado-Funktion berechenbar?

Wenn nein: Bedeutet das, dass man für kein n, z.B. n=4, einen Funktionswert angeben kann?

Ist das Halteproblem in der vorgestellten Form entscheidbar?

Wenn nein: Vollziehen Sie den Beweis nach, d.h. lesen Sie ihn und schreiben Sie ihn dann aus dem Gedächtnis, gern mit eigenen Worten, auf. (so nicht unmittelbar wichtig für die Klausur)

Page 48: Eine sehr kurze Geschichte der (theoretischen) Informatik Prof. Dr. Wolfram Conen, FH GE.

Quellen

Eine schöne Webseite Webseite zu Alan Turing hat sein Biograph Andrew Hodges zusammengestellt:, man kann natürlich auch gleich die Biographie lesen ;-)

Eine informatives Heft über Gödel gibt es im Spektrum-Verlag

Ein schönes, lehrreiches Buch zu den Hintergründen und Personen dieser Phase der Mathematik bzw. Informatik ist "Engines of Logic" von Martin Davis

Natürlich brauchen Sie all dies nicht für die Prüfung, aber wer sich ein bißchen für sein Fach interessiert, der schaut vielleicht im Laufe seines Studiums mal in diese sehr gut lesbaren Quellen - viel Spaß dabei!


Recommended