Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.1b1 Eine sehr kurze Geschichte der (theoretischen)...

Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.1b

1

Eine sehr kurze Geschichte der(theoretischen) Informatik

Prof. Dr. Wolfram Conen


2

Ziele dieser 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!


3

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?


4

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.


5

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...


6

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!


7

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]


8

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)


9

... 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)


10

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.


11

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.


12

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


13

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, dass 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!


14

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?


15

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


16


...... 1 1 1 1111

Zustand: z1

„Programm“

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

1


17


...... 1 1 1 0 0111

Zustand: z1

„Programm“

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


18


...... 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.


19

Die Turing-Maschine: Eine Aufgabe

Schreiben Sie ein Programm für die Turingmaschine,das eine positive Binär mit 2 multipliziert!

Zu Beginn ist die Maschine in einem Startzustand und steht ganz links auf der Eingabe, am Ende soll sie in einem Endzustand sein und nur das (korrekte!) Ergebnis soll auf dem Band stehen – wo derSchreib/Lese-Kopf dann steht, ist hier “wurscht”.


20

Die Turing-Maschine: Eine andere Darstellung

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

Das Programm zum „Umdrehen“ (Invertieren)von Nullen und Einsen kann man auch andersdarstellen:

z1 haltz1z1z1z1z1z1z1z1 ende

_/_,L

0/1,R1/0,R

Die Kreise markieren ZUSTÄNDE.Die Pfeile ZUSTANDSÜBERGÄNGE und Aktionen (Lesen/Schreiben, Bewegen)

Hier wird z.B. eine 0 gelesen, eine 1geschrieben, und dann erfolgt eineBewegung nach Rechts (R).


21

Die Turing-Maschine: Eine erste Lösung

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

Startzustand z1, wir stehen ganz links aufder Eingabe. Die Eingabe ist eine (positive)Binärzahl, es gibt also auf jeden Fall ein Zeichen unter dem Schreib/Lese-Kopf. Es muss nicht unbedingt eine1 sein (wir haben führende Nullen nicht verboten).

Idee: Laufe von links nach rechts über die Eingabe und bewege einfachjedes Zeichen um eins nach links. Hänge am Ende eine 0 an.

Anmerkung: In ihrem Mitschrieb haben sie gesehen, dass die Multiplikationmit 2 im Binärsystem dazu führt, dass man der Eingabe einfach eine0 „anhängt“ ... aus 1101 (dezimal: 13) wird also ein 11010 (dezimal: 26)


22


(z1,1) (0,z2,L)

(z2,_) (1,z3,R)

Wir lesen das erste Zeichen. Nehmen wir an,es ist eine 1. Dann „merken“ wir uns, dass wir eine1 gelesen haben, indem wir in den Zustandz2 („ich_habe_eine_Eins_gelesen“) gehen und zudem eine 0 schreiben (als „Platzhalter“, der besagt: hier war ich schon mal – wir könnten auchein „Sonderzeichen“, z.B. einen Stern * schreiben).Und außderdem gehen wir nach LINKS – klar, die1 soll ja nach links verschoben werden.Links von der eben geschrieben 0 muß nun eine 1geschrieben werden. Zu Beginn steht links von der Eingabe natürlich ein Leerzeichen. Dasüberschreiben wir durch die 1 – und wechseln dannin den Zustand z3, der besagt „habe eine Eins verschoben und muss nun nach rechts“


23


(z3,0) (0,z1,R)

(z1,0) (0,z1,R)

(z1,_) (_,ende,L)

(z2,0) (1,z3,R)

Im Zustand z3 überlesen wir die geradegeschriebene „Platzhalter-Null“ einfach, siewird ja gleich durch die nächste 1 über-schrieben – oder sie kann einfach dortstehen bleiben (denn eine 0 müssen wirnicht nach links verschieben, wir haben jadort schon eine 0 stehen!)Nach dem „Überlese-Zustand“ z3 kommt jetzteinfach wieder z1 – der „ich suche eine Eins“-Zustand. Wie gesagt, eine 0 kann bleiben, wosie ist (sie wird damit zur „neuen“ Platzhalter-Null.Wenn wir im „Suchzustand“ z1 ein Blank (_) finden,dann sind wir fertig!Wenn wir allerdings eine 1 finden, und dann nachlinks in z2 wechseln, brauchen wir noch einesinnvolle Antwort, denn dort „mittendrin“ ist keinBlank, sondern eine 0 ... fertig ist das Programm!


24

In einer anderen Darstellungsform

z1 z2 z3

halt

1/0,L

z1 z2z1z1 z2z1 z3z2 z3z2z1z1 z2z1 z2z1 z3

ende

z3

0/1,R

0/0,R

_/_,L

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

0/0,R

_/1,R


25

0/0,R

_/0,R

1/1,R

...und einfacher: 0 anhängen!

z1

ende

z1

1/1,R1/1,R1/1,R

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

0/0,R0/0,R

_ 1 1 0 1 0 _ _ _ _ __ _

_/0,R_/0,R

0

1/1,R

Lese nach rechts bis ans Endeund schreibe dort eine 0.


26

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


27

Universelle TM (2)

B0.UTM=1000000101110100000001010110100000010010110100001010110100000100010110101001110100000101010111010000111010000100101011101001001101000010100101101010001101000100010101101010100111010010101010010111010000011101000000000111010000001010110100000100101101001000110100010101001011010010001000110100101010001110101000011101001010010010111010010001001011010100010100111010010000001110101010010111010010010100111010101010101110100000011101001010101010111010000100110100011010001010000110100000101110101001010001011101000101010111010010000110101010010100101101010010110100100101011010100010101101001010010111010101000010011101001010101011101000101010011101010000101101010010001101010001010110100010000101110101001011010010010011010100101010110100100100010111010101000101110101010100011010101001010110100100010110101010100101100111010001001011101001000001110100010001011101001000110100000101011010010010010011101000010010110100100110100001010101101010010010111010011010000000111010001001010110100100010101110100010100101110101001000101110100100001011101001010001010111010100100010111010010010010111010010100010111010010010001110100101000011101000100011010010100100111010010001001110100001110100101001110101001001110100101001110100101010111010000001110101000100010111010100010100101110101000001011101001000001110101000010101101000100110101000100101110101001001110101001010111010010101001010111010100010010101110101010100010111010100100101011101000010101101010100010101100111010101010101001011010001010110101010000101110101010010010110101000000111010001000001110100010001110100001110101010100101011101010000010011101001010000011101000011101010100101110100100000101110100000000110100100110100001010101011010100000010110100001010101101000100110100001000011010001010110100000100110101001110100000010101011101001011010000100010110100001110101010010101011101001001101010101010101011010010011010001001010110100100101011101010101110101000110101010001010101101010000100101101010100101110100000001110100010100101011010010000100111010001010001011010000000111010001010010111010010001101000101010101011010010001101001000101010110100010000110101010101000111010101010100100111010010000100111010000001001101000001000110100100011010000100101101000101011101010010010011101010000011101011101010101010101010110100100101010101101010000100110100010100111010101010000111010101010100001110100001001011101010001011101010000111010010100101010111010100001110100101010001011101010000111010100010010111010001000101110101010101110101010011101001010101010101110101010011101010000101010111010000000011010000000101101010000100011010100000001101000100100011010001001001011010101001110101010000101110100000011101010010000101110101000000111010100100101010111010001101010001010101011101000110101001000101011101000000111010101000001011101000110101001001001011101000110101010101011101000101001110101001110100110101001010010101110100110101001010100101110100110101001010101010111010011010010101010111010010100011101001001101000100101101010100010010111010101001001101010010100110101000110101010010001011010100011010101001001010110100001011101010010101010110100100001101010100101010101101001000011010101010000101101001000011010000000001110100001011101010101001001011101000010111010101010010101011101000010111010010010001011101010000010101110100101000010111011011100111010100001011001110101010101010110100001011101010101000101011101000001010110101011010001001010101101001001010010110101001110100000100101011101000010101101010010100101101010011101000001010010111010101000101110100001

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


28

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)


29

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!


30

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


31

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


32

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


33

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


34

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


35

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


36

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) [Den Beweis schenken wir uns hier]


37

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“)


38

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)


39

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


40

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


41

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‘


42

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


43

Noch ein Beispiel...fleissige Biber Biber 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


44

Noch ein Beispiel...fleissige Biber Ein Biber 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 Biber wollen wir auch n-Biber nennen

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


45

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

soviele Einsen erzeugt, wie jeder andere n-Biber Unser Beispiel ist ein fleißiger 3-Biber Die Rado-Funktion Rado(n) gibt für n an, wieviele Einsen

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

haben Diese „Busy Beavers“ sind sehr schwer zu finden!


46

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


47

Warum? Zweitens... Da das Halteproblem nicht

allgemein lösbar ist, könnte es schwierig werden, nicht-haltende Lösungskandidaten zu erkennen...auch kleine Biber 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


48

Warum? Zweitens...

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


49

Warum sind fleißige Biber 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 f...also kann die Radofunktion nicht berechenbar sein!

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


50

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

Funktion F angeben:

F(x) = 0 · i · 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


51

Warum sind fleißige Biber 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


52

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

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 · i · 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!


53

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 eines zweiten Teils]


54

Einige Verständnisfragen

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.


55

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!

Date post:	05-Apr-2015
Category:	Documents
Upload:	claramond-nesser
View:	105 times
Download:	0 times

Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.1b1 Eine sehr kurze Geschichte der (theoretischen)...

Documents