[Playlisten] [Impressum und Datenschutzerklärung]

14.01 Turings Halteproblem

CC-BY-NC-SA 3.0

Nachtmodus Pausen an Schnitten Tempo: 0,5 0,7 1,0 1,3 1,5

Anklickbares Transkript:

heute – so zu umgehen wie man Fehler findet man Fehler vermeidet – wie man geschickter Weise – so programmiert – dass man Fehler – gar nicht erst einbaut – oder sich Fehler von selbst melden Punkt – ich möchte etwas anfangen was er abstraktes – junges Halteproblem – eine Perle aus der theoretischen Informatik – übrigens Halteproblem – einen Tuning – am – berühmter – Informatiker – er – wesentlich daran beteiligt die Geheimcodes – der – Deutschen im Zweiten Weltkrieg zu knacken zum Beispiel hat aber auch – sehr viel getan in Richtung theoretische Informatik – war das – einfachste – was es das einfachste das übliche einfache mathematische Modell des Computers stammt von ihm wenn es irgendwo sind die Turingmaschine – der Gedanke ist man hat einen – Tonband – auf den Daten gespeichert werden können – eine Maschine – wirst du mein Spulen kann hin und hervorgegangen – schreiben kann ?? lesen kann und dann hat man Zustandsautomaten – der – das ganze steuert – die Turingmaschine – einfaches Modell für ein Computer falls es jemals sehen das es kein praktischer Computer aber hilft in der Mathematik einige Sachen zu beweisen ?? Computer – only habe jetzt das – thüringische – Halteproblem – das alte Problem – ist die Frage ob ein gegebenes Programm – anhält sie kennen das von üblicher Software – hin und wieder – hängt die Software – ?? wird mit irgendeiner Aufgabe nicht fertig sie sagen – lade folgende Datei – oder – für diese oder jene Berechnung aus – der Formatierung – und was immer das Programm hängt und wird nicht fertig das wäre das Gegenteil von Halten – die Frage – hier ist hält ein bestimmtes Programm an wir dieses Programm fertig – oder läuft es – unendlich lang weiter das übliche Beispiel für ?? die Langlauf das Programm gerne Endlosschleife – Programm was in Endlosschleife – hängt – hält nicht an – dann geht's bei dem Halteproblem – an – wenn man sagen könnte – ob ein Programm anhält hätte man schon – naht Fehlertag automatisch durchgeführt – darum geht's danach ?? dabei – es ?? guckt man sich über bestimmte Programme an – Herrn nicht alle möglichen Programme nicht sowas wie Microsoft Word – nicht sowas wie Firefox nicht ganz ?? Bezieher sehr Simpelprogramme – wenn sie im Buch über die Richformate – gucken sehen Sie etwas andere Programme als ich das jetzt beschreibe – ich möchte dich möglichst billig halten – möchte ich gerne Programme – mir angucken – die eine Datei einlesen das soll mein Programm sein – ich auf Beistrich dass im Text das soll mein Programm sein das Programm soll eine Datei – beliebiger Länge – beliebigen Inhalts einlesen – und dann eine Zahl ausspucken – das ist – meine Billigversion von Programmen die ich heute betrachten will an der Stelle – gesagt die übliche Literatur guckt sich andere Programme an das was ich mir ?? – Datei rein eine Zahl raus alle Programme – auf einer gegebenen Maschinen – in eine gegebene Programmiersprache – so genau sich angucken – die sie schreiben können all diese Programme möchte ich mein Kopf der Datei einnehmen und eine Zahl – raus geben – zwei – dumme Beispiele dafür für solche Programme – ?? die kriegen was man damit machen könnte ?? ich könnte – die Zahl der Bytes – der Datei ausgeben – Falls ich gucke gar nicht genau rein – was in der Datei steht – ?? Programm zählt einfach wie viel Bytes in der Datei drin sind und gibt diese Zahl aus wie ein ganz – dummes Programm dieser Art – an – ein anderes dummes Programm dieser Art wäre ich mal das mal als Flussdiagramm – wäre folgendes – State – lese die Datei ein das wäre dann ja eine Eingabe – so auffasst – ?? einlesen – ?? Eingabe des – Film – unter mache ich folgendes – ich prüfe die Länge – dieser Datei – größer gleich zweiundvierzig – Bytes ist – Fragezeichen – Test – an – wenn das der Fall ist – Komma wird ergänzt wenn das der Fall ist – ewig – sieben aus – und – bin fertig – wenn – das – nicht der Fall ist – setzt sich – eine Variable A auf dreizehn – und geht dahin zurück – setze noch mal die Variable auf dreizehn gehe dein Zurücksetzen noch mal die Variable auf dreizehn und so weiter sofort – in das Programm ist schon bisschen – ekliger ist Komma hängt – in dieses Programm eine Datei sieht – die kürzer ist als zweiundsiebzig Bytes – wird es jene Endlosschleife hängen da unten – das wäre auch ein erlaubtes Programm – aus dieser Menge – aller Programme – auf einer gegebenen Maschine in einer gegebenen Sprache – die – Dateien einlesen und Zahlen ausgeben – nimmst – wenn es was ausgeblendet – dessen Zahl aus – aber es ist nicht sicher das was das was ausgibt – es gibt Fälle den dieses Programm hängt nicht hält – den am Halsproblem – an – es gibt Fälle in denen dieses Programm nicht hält in denen es – unendlich lange – arbeitet – und eben – nie was ausgeht – in diesem Fall gibt es irgendwann das ?? was aus – an – ?? vorstellen dass dieses Programm auch – vernünftige Sachen machen könnten – dann – könnten vielleicht – die Zahl Pi auf drei Millionen Stellen nach dem Komma berechnen – zu einem Programm – werden – sie könnten ?? große Datenbank reinschmeißen – und fragen wie viele Leute – von den Leuten in der Datenbank – sind älter als fünfundsechzig – und da mein Jahreseinkommen – unter zwei tausend Euro und so weiter – also viele sinnvolle Programme lassen sich so auffassen sind ?? Dinge drin was ich aufgeschrieben habe sind zwei – nicht so richtig sinnvolle Programme – des mal sehen was will man sie passieren – ein – Mann nimmt noch etwas weiteres an das es Beistrich die man nimmt an dass der Rechner das dies der dieses ausführt immer genug Speicher hat dieses Programm was da läuft – soll in der Lage sein wie lieb ich aber endlich viel – immer nur beliebig viel Speicher anzufordern – kann sie sich so vorstellen ?? das Programm merkt auf ?? bin ich in mein vier Gigabyte am Ende – haben ?? – dann gibt's die Meldung und sagt bitte jetzt gleich einmal in den nächsten Laden und wohl nochmals sinnigerweise – stecken die Finger weit rein das Programm macht weiter heutige Software arbeitet so nicht – absurderweise – vielleicht sogar ein bisschen aufwändigste zuzuschreiben – an – dieses Programm soll – immer genug Speicher haben – in dem – Sinne – wenn es mal nicht genug Speicher hat kann ich Ihnen angehen und neun Speicher kaufen und der Rechner soll das ?? auch beliebig viel Speicher – fressen aus der Rechner soll jetzt nicht auf die Gigabyte beschränkt sein sondern wenn's nötig ist dann müssen eben auch – eine hundert Million Terabyte gehen – theoretisch alles gesehen das es schon bisschen hakelig an der Stelle – beliebig viel Speicher darf ich nehmen solange es den endlich vieles – das man das ganze – erst mal einfach – ist aber danach auch ein Kritikpunkt – es es etwas abstrakter als man es in der Wirklichkeit hat Rechner mit – mit beliebig viel Speicher wenn es denn nur endlich viel weiter – nun – kommt – der große Klimmzug – von Herrn Duering – besteht im theoretischen – Buch über theoretische Grammatik etwas anders nicht wundern wenn sich Nachschlag – typischerweise das etwas kompetenter verkauft – der – große Klimmzug ist der folgende – wenn sie so ein Programm haben – welches auch immer – ist das ja auch wieder dieses Programm hier ist ja auch wieder eine Datei – das Kind sieben Sie einfach – sich in den Programme Ordner angucken auf der Festplatte jedes Programm ist – als ?? als Datei oder sogar Sammlung von Dateien in ?? bei der letzten der Minister nimmt – es als Sammlung von Dateien abgebildet war ?? zwar ein Verein Programm ist auch wieder eine Datei – das heißt ich könnte auch – solche Programme – mit Programmen füttern das wäre auch möglich weil ein Programm eine Datei ist – neben sie ein Programm – füttern es – das Programm oder wenn sie ganz hart drauf sind sogar in dasselbe Programm – und dann kommt eine Zahl raus – das wäre möglich mit diesen Programmen sie können diese Programme die ja für sich – auch wieder Dateien sind – in andere Programme von dieser Art reinstecken – und – eines dieser – einen ein Programm was sehr spannend wäre – was es leider nicht gibt den Vergleich wäre eines das prüft – ob ein anderes Programm hält – dass das Halteproblem – löst – so ein Programm hätte ich gerne – da – es ist der Wunsch steht im Text der Wunsch ist – ein Programm T folgender Art – Programm wenn Sie so wollen – das automatisch – auf – hängende – Software prüft – ein Programm – wie – also – ich hab so ein Programm wie folgende Art hätte ich gerne – schließt folgendes ein – Index Nummer zwei – es – sollte eine Datei – einlesen – haben – ?? etwas komplizierter es liest nicht nur einfach – irgendein Programm ein – Programm besondere Programme prüfen – soll ?? für die Datei des Programms – eines anderen Programms einlesen – ?? noch eine Eingabe dazu – als was ist es eine Datei eines Programmsprogramms – gerne – nicht das andere Mal – und dahinter noch eine Eingabedatei – für das ob dahinter – noch eine Eingabedatei – für dieses andere Programm eher dahinter – Eingabedatei – die – das wird ja beides zusammen können Sie wenn Sie wollen's beides zusammen eine Datei kippen – müssen müssen vorsichtig sein – müsse davor verschreiben – wie lang nicht weiter müsse der vorschreiben wie lang diese Datei ist – an – damit – das Programm nachher diese beiden Bestandteile der Datei auseinanderhalten – kann – Kleinkram will ich nicht drauf eingehen – also das soll mein Programm P können – als Eingabe – erwartet es – eine Datei – in der steht – am Anfang ein anderes Programm – und dahinter – die Bytes kopiert von einer Eingabedatei – und die Ausgabe – soll sein – Zahl eins oder die Zahlen null – die Programme die ich angucke soll ?? Zahlen ausgehen sie soll es soll die Zahl eins dieses Programm P soll die Zahl eins ausgeben – wenn – das Programm eher – mit der Eingabe die anhält – nicht hängt – wenn es also funktioniert – und es soll die Zahl null ausgeben – es nicht funktioniert – das hängt – sozusagen – nicht anhält – das in endlicher Zeit – das Programm eher – in endlicher Zeit auf die Eingabe die – keine Antwort liefert sondern – hängt – müsste jetzt noch – eine mögliche Fusion dazuschreiben – dann – dieses Programm was ich ja habe sollte eigentlich beliebige Dateien verarbeiten – was ist denn am Anfang nicht die Datei eines Programms steht sondern Müll müßig innerer Extrafall haben ?? gebe – achtundneunzig aus wenn am Anfang Müll steht – oder gebe sogar weiterhin null aus dem Anfang besteht – Beistrich nicht zu kompliziert machen halt was dabei so ein Programm erträumt man sich wenn man – Software automatisch testen will – ich möchte ein Programm – das ein anderes Programm einliest – und eine Eingabedatei – für das andere Programm – von mir dann sagt – in endlicher Zeit – wieder ?? Ausgabe haben – mir dann sagt das andere Programm bei dieser Eingabe anhält – oder ob es Probleme hat und nicht einhält – wären automatischer – Test für beliebige – Programme – stellt sich dann heraus okay so ein Programm kann es leider nicht geben – es gibt keinen universellen – halte Tester wenn Sie so wollen – also man erträumt sich sein automatisches – Prüfprogramm – das mir sagen kann in endlicher Zeit sagen kann – ob ein gegebenes – Programm – einer gegebenen Eingabe – hängt – oder nicht – dass das Halteproblem – löst – ein Problem ist die Frage ob ein gegebenes Programm bei gegebener Eingabe – hält – stellt sich leider heraus so ein Programm kann es nicht geben in dieser – allgemeinen Form – ?? – um das zu sehen – kann man eine ein weiteres Programm bauen – wenn es das Stück ?? Text – wenn es dieses Programm die universellen Tester gäbe – dann könnte man ein anderes Programm bauen – von dem anderen – relativ einfach sieht das dieses andere Programm einfach nicht klappt – am – folgendes andere Programm könnte man Bau – schreib das erwidert Flussdiagramm – das andere Programm – es liest – das ?? all diese Programme machen es liest eine Datei ein – diese Datei die – dann – sagt es die Variable A ist das Ergebnis – wenn ich das Programm P von ebendiesen universellen Tester mit folgendem füttere – so diverse Tester erwartet er zwei Sachen hintereinander – in einer Datei ich füttere den mit folgenden – der Inhalt der Datei und dahinter schreibt noch mal den Inhalt der Datei sieht völlig – absurd aus und sehen das ergibt gleich – sind es bricht ?? bricht alles zusammen wenn man das veranstaltet – dann – als ich lese eine Datei ein was ich mache ich schreibe diese Datei zweimal miteinander – und übergebe dir mein Programm die – universellen Tester und merke mir das Ergebnis – das komisch aussieht mich nicht wundern ?? sie sind gleich – Komma sondern Konzeption acht – das Ziel ist hier nicht etwas sinnvolles zu berechnen das Ziel ist nur zu zeigen dass es diesen universellen Test HP nicht geben – und etwa zwei glich – aus B kommt ja – nur raus oder eins raus – in endlicher Zeit – ich – prüfe ob A gleich eins ist – also – dieser Tester – sagt das es okay – wenn der Test sagt es ist okay – Jahr – gegen ein Endlosschleife – was das Endlosschleife sieht schön aus wenn der Tester ja sage ich in eine Endlosschleife – den sich einfach vor ?? ?? Befehl weiter zu – an wenn der Tester sagt nein – da – es gibt ein Problem – gebe ich irgend eine Zahl aus natürlich zwoundvierzig – denn Informatik hier und Ende – Richard – ?? Klammer zu gesagt wenn sie in ein Buch über die Referate gucken oder Wikipedia gucken und Halteproblem – sieht das etwas anders aus ?? versucht es so billig zu machen wies geht – das ist mein Programm Punkt – wenn es dieses Programm regelt – und das funktioniert das Programm P – angenommen das wäre so dann kann ich das Programm Q bauen auf diese Weise nicht die Militäreinsätze – sind das Programm Kuk ist wieder von der gleichen Art wie die anderen Programme – es liest was ein und gibt eine Zahl aus – oder hängt – also genau von derselben Art wie die anderen Programme – und jetzt kommt der Kunstgriff – von Herrn Johann wie gesagt Pensionen und der – sieht etwas anders aus etwas komplizierter als das was ich jetzt mache – der Kunstgriff des folgender dieses Programm Q – ist ja auch wieder eine Datei – das heißt dieses Programm – könnte sich selbst einlesen – dieses Programm frisst – Dateien – ich füttere dieses Programm – mit sich selbst – das ist das völlig absurde Idee ein Programm mit sich selbst zu füttern da das zeigt weiter nochmals – Punkt – Pech für drei Programme mit sich selbst nehmen sie hier den Editor – und dann öffnen Sie – den Editor – auch ?? ?? ist in Deutschland in – einfacher – Arsystem – zwei tausend ?? – so jetzt aber – es Dorfgründungen – Komma System zweiunddreißig – keine Textdatei – sondern – Datei – die – L M N Nahrung – Texte – der habe ihn doch öffnen – ich öffne Notepad Echse mit dem Editor Notepad Excel – das es beklagt aber – möglich – es ist nur der Texte in ?? Texte geöffnet – mit der sie von NSG Sie können ein Programm – mit sich selbst aufmachen warum nicht im allgemeinen ist es ziemlich schwachsinnig wie hier – ?? hier dient es gleich als – komisches Beispiel – um zu zeigen dass das schief geht – dieses Programm hier – wird eine Datei sein und was ich mache ich nehme diese Dateien und füttere die in das Programm rein – und frage mich dann – ob dieses Programm endet wenn ich es mit sich selbst füttere – oder nicht – große – Frage bin ich Kuh dieses Programm Q mit sich selbst füttere endet das wurde nicht – angenommen es endet Punkt was dann passiert – angenommen – endet heißt es hält – bei Türen – ich ?? verschreiben hält das schöne angenommen – es hält – Komma sondern was dann passiert ?? angenommen es hält nicht wenn ich es mit sich selbst füttere – einer – von diesen beiden Fällen muss ja auftreten – entweder es hält oder selten ich wieder notwendiges mit sich selbst füttere – so – wenn es hält – wenn es hält – was es dann passiert ✂ wenn dieses Programm hält – Sinnes kann nicht mit der Endlosschleifen – geendet haben – werde es auch nicht entweder Endlosschleife es muss hier gelandet sein wenn es hält muss es hier gelandet sein und zwei wird sie ausgegeben habe ?? das heißt – A muss ungleich eins gewesen sein – das heißt – dieser Test muss fehlgeschlagen – sein dieser Test hier muss gesagt haben – wenn ich das Programm Q – mit dem Programm kuhfüttere – hält es nichts – wenn das Programm hält lerne ich – es muss so gewesen sein das es nicht hält – das haut irgendwie nicht gut hin – ?? sagen es ist schwarz daraus folgt ist es weiß das kann nicht sein wenn dieses Programm anhält – hätte es zweiundvierzig – ausgegeben – A hätte – gleich null sein müssen nicht gleich eins sein müssen A gleich null heißt aber dass dieser Test HP – wenn ich frage – ob das Programm Q – Q rein ob das Programm ?? mit der Eingabe Q anhält dass der Tester gesagt hat das Programm nicht an mit anderen Worten – den Kuchen mit Eingabe Q anhält habe ich gelernt – es ist nicht anders ein Widerspruch das kann nicht sein – und sie an was passiert – wenn man probiert – okay dann hält es wohl nicht an ?? angenommen – ich füttere hier Kuhreihen – dieses Programm hält nicht ?? dann hätte ich hier in dieser Endlosschleife – landen müssen denn sonst – wäre ich da also das letzte was dieses Programm tut – was hat das letzte was es auf Dauer tot ist die Endlosschleife – wenn es nicht halten würde – wenn dieses Programm nicht halten würde müsste sie in der Endlosschleife landen – also wäre A gleich eins – also hätte dieser Tester gesagt – wenn ich das Programm Q kommt der Koran mit Kuh füttere – hält es an – die hätte eins geliefert – der Test ?? gesagt – Q von Q hält an – sie in keinem von den beiden Fällen – aus zehn – ?? kleines Problem – einen logischen Widerspruch – dieses Programm Q kann es nicht geben – aus diesem Widerspruch – dieses – Programm – kann es nicht geben – was hätten wir einen großen Widerspruch produziert – erinnert sich noch an an den Beweis – darum wozu zwei – keinen – Bruch zweier natürlicher Zahlen ist das geht zu ähnlich meinem Tanne sei ein Bruch zweier natürlicher Zahlen stellt fest – auch nicht hin – das ist – so ähnlich – angenommen – es gäbe so ein Programm Q stellen sie fest so hat nicht den Scan nicht funktioniert ?? zumindest kann es nicht von singen wenn ich es selbst – in sich selbst eingeben – was gibt zumindest einen Fall in dem Hilfsprogramm – nicht richtig funktionieren kann – wenn es das Programm Q nicht geben kann – ?? das macht ja nun wirklich nichts Besonderes das Programm ist dies was ein Ruf an das Programm auf – Endlosschleife – Verzweigungsausgabe – des Programmcodes wirklich völlig billig wenn das Programm Q nicht geben kann dann kann es auch das Programm P nicht geben – das ist das einzige woran es scheitern kann – als Google nicht geht kann es wenige – P – war dieser universelle Tester – ob ein Programm halt – anhält – mit anderen Worten es gibt keinen solchen universellen Tester der sagen kann ob ein beliebiges – Programm – bei einer beliebigen Eingabe anhält – dazu können zumindest einen Fall konstruieren bei dem es schief geht – das – zeigt dass dieses Halteproblem – fieser ist als man sich so vorstellen kann ?? – es gibt keine universellen Tester – an – ?? muss aber bisschen vor Versand das zu interpretieren ?? System theoretische Informatik – zwei Randnotizen – zur Interpretation – dieses Resultat – typischerweise – verkauft – und es gibt keine Jones universell zu testen – an – der Garten wir wollen im allgemeinen auch nicht – universell testen – denn – wie es dasteht – wie das jetzt gebautes müsste P – also P muss – beliebig komplexe – beliebig – komplexe – Programme verarbeiten – beliebig komplexe – Programme verarbeiten beliebig lang – beliebig – tief verschachtelte – Schleifen – verschachtelte Hilfs – ?? ich immer nur endlich trotzdem – aber – von mir aus – über zehn Millionen weil ineinander verschachtelt müsste B verarbeiten muss beliebig konvexe Programme verarbeiten – wenn ich das eingeschränkte – gilt dieses Argument nicht – was passiert wenn ich – mich einschränke – kann man sich fragen was passiert – Fan – nur – bestimmte Längen erlaubt sind – nur Programme – bis ein Kilobytes – was ist wenn nur bestimmte Konstrukte erlaubt sind – haben – ?? Bindestrich Längen erlaubt sind – denken – erlaubt – sind – und so weiter – was ist wenn ich das einschränke – dass das Programm – dass die Programme die verarbeitet werden müssen von diesem Tester nicht beliebig komplexe – dann bricht dieses Argument zusammen – also da vorsichtig sein – und das andere ?? vor sich sein muss dass Babys jetzt gebaut ist muss – exakte Resultate liefern – ja oder nein muss die Antwort sein – muss exaktes – Resultat liefern – an – was passiert – wenn man mit neunundneunzig %iger Wahrscheinlichkeit zufrieden ist – dann durch das Argument schon wieder zusammen – hatte dieses Argument von Herrn Duering sagt nicht sie können – verbietet nicht das ein Tester bauen der neunundneunzig von hundert Fällen das richtige sagt – das will es nicht ausschließen – was ist ?? mit neunundneunzig Prozent wahrscheinlich gar zufrieden – wenn – Sie ein Programm vor – das einfach – mit trinken was darunter klingelt und sagt Vorsicht – mal nach uin uin Rechtschreibprüfung – die Rechtschreibprüfung – ist wahrscheinlich sogar in – nur neunzig von hundert Fällen – und weniger sogar noch weitere neun siebzig von hundert Fällen korrekt und trotzdem ist welcher Prüfung hilfreich – darüber gibt's ja bei dir sagt dieses Argument nicht dies Argument geht nur – durch wenn ich verlange dass dieses Programm dieser Test ein hundert Prozent – immer der Fälle funktioniert – sobald ich das erlaube das in ein Prozent nicht funktioniert bricht das Argument zusammen wenn man in ?? – zufrieden ist – allerdings – ist Acme nicht zu streng – an – ein klassisches Resultat – an zum – Testen von Programmen zum automatischen Testen von Programmen kann ich automatisch – feststellen ob ein Programm bei der gegebenen Eingabe anhält oder nicht – geht nicht universell – aber eigentlich – wolle das auch nicht universell seicht nur das ist doch verdammt schwierig ist und allgemein Texte zu schreiben – immerhin das zweites – es wird schon was komisches passiert man das anfängt – nicht desto trotz – hoffe das offensichtlich wenn ich Längenbeschränkungen – einbaue – habe ich eine Chance – wenn ich und andere Kapazitätsbeschränkungen – einordnen schon wenn ich – juristische Verfahren habe – die einfach nur typische Fehler rauspicken – ?? dann eben nicht mit hundert Prozent wahrscheinlich ganz sagen nicht exakt sagen ob ich Problem habe sondern mir nur andeuten das irgendein Problem sein könnte dann halt auch – also – mindestens zwei Körnchen Salz bei diesem theoretischen Resultat