Bestand wählen
Merken

14.01 Turings Halteproblem

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
Ursus und man Fehler findet man viele formale der Geschichte war es so programmiert dass man da gar nicht erst eingebaut oder sich weder von selbst sprechen wird was anfangen was ja abstraktes Jungens Halteproblem eine Perle aus der theoretischen Informatik das Halteproblem kommen
Berühmter Informatiker es sich daran beteiligt die der einen kurz der deutschen 2. Weltkrieg zu knacken zum Beispiel hat aber auch sehr viel getan in Richtung Theoretische Informatik das fast das ist es einfach sie das übliche einfache mathematische Modell des Computers stammt von eines vorsehen Maschine der Gedanke ist man hat ein Tonband auf die Daten gespeichert werden können eine Maschine Wie das Tomasz wurden kann hin und her von schreiben kann lesen kann dann man Zustandsautomaten der das ganze steuert die Tuner Maschinen einfach für Computer falls es jemals das ist kein praktischer Computer aber gilt in der Mathematik einige Sachen zu beweisen Computer und mir aber jetzt das führend Halteproblem das Halteproblem ist die Frage ob ein gegebenes Programm eine hält sich das von durchaus auch für und wider die Software wird mit einer Aufgabe nicht fertig sagen Lacherfolge das eine oder für diese Größe Berechnung aus der Formatierung und was auch immer das Programm wird nicht fertig das wir das Gegenteil von halten die Frage wie es hält ein bestimmtes Programm an wird dieses Programm fertig oder läuft es Bandbreite weiter das übliche Beispiel für die man auf das Programm der eine Endlosschleife Obamas was Endlosschleife Hält nicht an Darum geht es bei den Halteproblem wenn man sagen können ob ein Programm anhält hätte man schon derart viele Check automatisch durchgeführt darum geht es dabei erst kurz man sich über bestimmte Programme und nicht alle möglichen Programme nicht so was wie Microsoft für nicht so was wie Firefox nicht so kompliziert sehr sind Programme sie hoch über theoretische normative sind sie etwas andere Programme als ich das jetzt beschreiben und ich mich wirklich möglichst billig also möchte ich gerne Programme wir Gruppen die eine Datei einlesen das sondern Programm soll nicht auf Aufwand steht als wächst das zum Programm sein das Programm soll eine Datei beliebiger Länge beliebigen ein lesen und dann eine Zahl Ausspruch das ist meine Billigversion von Programmen die heute betrachten will an der Stelle gesagt die in der Natur gut sich andere Programme und das ist was der Datei eine Zahl aus alle Programme auf einer gegebenen Maschinen in die Programmiersprache Supermaus aus ankucken die Sie schreiben können also Programme möchte ich mir die der Fall war und eine Zahl ausgeht 2 willst du Beispiele dafür für solche Programme für die kriegen was man damit machen könnte ich könnte die Zahl der Reiz der Datei aus das was ich gucke dann nicht auch eine was in der Datei steht das Programm zählt einfach Life Balls Wörter und sind die diese Zahl aus einem ganz bewusst Programm dieser Art
Ein anderes Programm dieser Art wie ich mal das mal als lustige folgendes ich starrte lese die Datei ein das bildet eine Eingabe so auf fast Zeit einlesen Eingabe und dann mache ich folgendes ich prüfe ob die Länge dieser der Zahlen
Größergleich 42 als ist Fragezeichen Des
Wenn das der Fall ist Und verteilt werden das der Fall ist wir 7 aus Und fertig Wenn das nicht der Fall ist
Setzt sich eine Variable auf 13 Und jeder zurück setzte noch mal die Variable auf 13 gilt als zurücksetzen noch mal wieder auf 13 usw. sofort das Programm ist schon ein bisschen wieder von Hand dieses Programm eine Datei sie die kürzer ist als 42 als gibt es in der Endlosschleife der und das wäre auch eine erlaubt das Programm aus dieser aller Programme auf eine gegebene Maschinen einer Sprache die Dateien diesen Zahlen aus wenn es was aus gibt es aus aber es ist nicht sicher dass wir das ist was aus gibt es gibt Fälle dieses Programm nicht als Problem
Dieses Programm nicht hält den es unendlich langen arbeitet und niemals ausgibt in diesem Fall gibt es irgendwann das was aus am Situation vorstellen dass dieses Programm auch vernünftige Sachen machen können
Der könnten vielleicht die Zeit die auf 3 Millionen Stellen nach dem Komma berechnen zu einem Programm sie können große Datenbank reinschmeißen und fragen wie viele Leute von Leuten in der Datenbank sind älter als 65 und ein Jahreseinkommen unter 2 Tausend Euro und so weiter und so viele sinnvolle Programme lassen sich so auffassen sind dass sich aufgeschrieben haben sind zwar nicht so wichtig sind von Programmen für das was uns passieren kann man noch etwas weiter anders ist das tritt an dass der Rechner dass diese dieses ausführt immer genug Speicher hat dieses Programm was da läuft soll in der Lage sein die nicht aber ich viele immer nur beliebig viel Speicher anzufordern das können Sie sich so vorstellen das Programm merkt Auge ich meinen 4 GB und dann gibts sagte die Slash aber nächsten Daten und wohl noch mal 4 GB sie steht die beitragen das Programm macht weiter heutige so verarbeiten so nicht absurderweise vielleicht sogar ist auch ein bisschen auf zuzuschreiben dieses Programm soll immer genug Speicher
In dem Sinne dass man nicht genug Speicherplatz hat gar nicht da die neuen Speicher kaufen der Rechner soll auch wichtig bei der fressen also der Rechner soll jetzt nicht auf die Gewalt beschränkt sein sondern wenn es nötig ist müssen auch 100 Millionen der Arbeit die theoretische ist das ist schon bis inhaltlich an der Stelle beliebig viel Speicher darf ich solange es endlich viele ist also macht das Ganze erst mal einfach ist aber danach auch ein Kritikpunkt ist ist etwas abstrakter als man eines der Wirklichkeit hat Rechner mit mit beliebig viel Spaß und wenn ist nur die Frage kommt der große Klimmzug von Theorie besteht theoretischen worüber theoretische Grammatik etwas anderes nicht wundern wenn sich nachschlagen typischerweise wird etwas komplizierter verkauft der große Zug ist der folgende wenn sie so ein Programm haben welches auch auf ist das ja auch wieder dieses Programm ist ja auch wieder eine Datei dass Sie wenn Sie einfach sich die Programmordner ankucken auf der Festplatte jedes Programm ist als als Datei oder sogar Sammlung von Dateien erscheinen und bei der Welt ist es als Sammlung von Dateien abgebildet bereits einfach Programm ist auch wieder eine Datei das heißt ich könnte auch solche Programme mit Programmen führte er das wäre auch möglich weil ein Programm eine Datei ist sie ein Programm führte es in ein anderes Programm oder wenn sie ganz hat auf den sogar dasselbe Programm und dann kommt eine Zahl aus
Das wäre möglich mit diesem Programm sie können diese Programme die dafür sich auch wieder Dateien sind in andere Programme von dieser Art reinstecken und eines dieser Einen eigenen Programmen was sehr spannend was es leider nicht wäre eines des prüft ob ein anderes Programm hält es das Halteproblem löst so ein Programm mit der das ist der Wunsch steht Text der Wunsch ist ein Programm von mehr als
Ein Programm wenn Sie so wollen das automatisch auf hängen der Software prüft ein Programm was ich schwarz ein Programm für die folgende als hätte ich gerne Es liest folgendes an der Freien Es soll eine Datei einlesen als etwas komplizierter schließt nicht nur einfach ein Programm ein bis Programm des Sonderprogrammen prüfen es soll verhindert eines Programms eines Programms ein Wesen Soll auch noch eine Eingabe dazu also dieses eine die Datei eines Programms Programm das Er das andere Mal Und dahinter noch eine Eingabe für das ob dahinter noch eine Eingabe für dieses andere Programm aber dahinter war der Zeit des das sie aber beides zusammen können Sie wenn Sie wollen zu beides zusammen eine Datei gibt müsste müssen vorsichtig sein müsse der Vorfreude schreiben sie darf nicht weit und müsse vorschreiben wie lange diese Datei ist damit das Programm nach diese beiden Bestandteil der Wörter auseinander als Kleinkram nicht auf eigentlich also das Sonderprogramm können als Eingabe erwartet ist eine Datei in der steht am Anfang ein anderes Programm und dahinter die bereits kopiert von einer Eingabe der Und die Ausgabe soll zur
Die Zahl 1 oder die Zahlen 0 die Programme die ich gucke soll nur Zahlen aus geben sie soll es soll die Zahl 1 dieses Programm P soll die Zahl 1 ausgeben wenn das Programm er mit der Eingabe des einhellig nicht
Wenn es also funktioniert Und das soll die Zahl von ausgeben Wenn es nicht funktioniert Wenn das sozusagen nicht an das in endlicher Zeit das Programm der sich Zeit auf die Eingabe die keine Antwort sondern hängt müsste jetzt noch am Fuß oder zu schreiben dieses Programm was sich aber sollte eigentlich beliebige Dateien verarbeiten was ist der am Anfang wichtiger Teil eines Programms steht sondern sich auch extra von 98 aus werden am Anfang steht oder sogar nur aus und möchte ich jetzt nicht zu kompliziert machen halt was dabei so als Programme träumt man sich immer so automatisch testen will ich möchte ein Programm
Das ein anderes Programm einliest und eine Eingabe für das andere Programme und dann sagt in endlicher Zeit Bildern Ausgabe haben wir dann sagte das andere Programme bei dieser Eingabe anhält oder ob es zu Problemen nicht an Das deren automatischer Test für beliebige Programme und stellt sich dann heraus ok so ein Programm kann ich leider nicht es gibt keine universelle High-Level-Test da dieser vor
Also träumt sich sollen automatisches Prüfprogrammen was mir sagen kann in endlicher Zeit sagen kann ob ein gegebenes Programm einer gegebenen Eingabe hängt oder nicht Dass das Halteproblem als Problem ist die Frage ob ein gegebenes Programm bei Eingabe hält stellt sich leider aus so ein Programm kann es nicht geben dieser allgemeinen Form Um das zu sehen
Kann man eine ein weiteres Programm bauen Wenn es darstellt und jetzt wenn es dieses Programm die universelle des der Dann könnte man ein anderes Programm bauen Von dem anderen relativ einfach sieht das dieses andere Programme einfach nicht klar warum folgendes andere Programm könnte man auch Erschwert das mal wieder Flussdiagramm das andere Programme ist liest das ohne alle diese Programme machen es liest anderthalb Diese Datei Da Sagt die Variable a ist das Ergebnis wenn ich das Programm des von diesem universelle Test mit folgendem führt so universell beliebteste erwartet der 2 Sachen hintereinander in einer Datei ich führte wird mit folgenden Inhalt Datei und der erschrak ich noch mal den Inhalt der Datei besteht völlig Absurd aus sehen dass gleich sind es bricht Daten bricht alles zusammen wenn man das veranstaltet also schließe eine Datei ein was ich mache ich schreibe diese Datei zweimal hintereinander und übergeben die ein Programm das universelle Tester und merken das Ergebnis Wenn das komische aus ich mich nicht wundern wenn sie sich überall um unseren Konstruktion war das Ziel ist nicht was sinnvolles zu berechnen das Ziel ist nur zu zeigen dass es die so sehr daß er nicht und wird von 2 aus P kommt ja nur aus oder eines raus als
Ich prüfe ob war gleich 1 ist Ob aber so dieser 1. sage das ist ok wenn Tester sei das ist okay Ich ja Die ich in eine Endlosschleife Was das für Schleife sich zwischen der des da ja sagte ich in eine Endlosschleife den sich einfach vor dass dann wird es der Wahl zu Wenn der 1. sagt man Es gibt ein Problem gebe ich eine Zahl aus natürlich 42 Ist in der Informatik hier und Sicherheitshalber zugesagt den sie worüber theoretisch Mathematik gucken oder Wikipedia gucken Dokumente Halteproblem sieht das etwas anders aus der Besuch des so billig zu machen ist das ist warm Programmcode
Wenn es dieses Programm gegen die Und das funktioniert das Amt des angenommen dass wäre dann nicht das Programm von bauen auf diese Weise nicht Sätze sie das Programm Q ist wieder von der gleichen Art für die anderen Programme es liest was ein und die Anzahl aus oder hängen Also auch von der Art wie die anderen Programme
Und jetzt kommt der Kunst von Enzio gesagt oder dieser was anderes aus etwas komplizierter als das was ich jetzt mal den Kunstgriff ist folgender dieses Programm Q
Ist ja auch wieder eine derzeit das heißt dieses Programm und konnte sich selbst ein Dieses Programm früher Dateien ich für wird dieses Programm sich selbst
Bei ist das natürlich absurd die ein Programm mit sich selbst zu füttern das sei vielleicht dann einmal pro vorbei Woche recht führte ein Programm mit sich selbst nehmen Sie Herr der Erde zur
Und öffnen Sie gemeldet worden wo auch immer größte und
Das doch der
So sein Gar bis 32 wurde der Text so jetzt aber Restaurant würde ich mich das Änderungen und ich glaube das ist 32 natürlich keine Textdatei sondern die Datei
Zum Ort der 6. haben doch öffne ich eröffneten Robert Echse mit dem Zuordnung der wächst das ist beklagt aber wird das ist nur der 6. unterwegs sind also nicht dass von der des geht sie können ein Programm mit sich selbst machen warum ich im Allgemeinen ist es ziemlich schwachsinnig hier
Hier dient es gleich als komisches Beispiel und zu zeigen dass was schief geht dieses Programm
Wird eine Datei sein und was ich mache diese Dateien und führte die das Programm und frage mich daran ob dieses Programm endet wenn ich es mit sich selbst führte wird oder nicht
Große Frage nicht cool dieses Programm mit sich selbst führte das wurde nicht angenommen es letzten und was dann passiert eingeladenen es mit heißt es hält bei Tieren und ich verschwand für einen Namen das gleiche anders als jetzt an Namen es nicht wenn ich es mit sich selbst mit
Einer von diesen beiden Fällen muss ja auftreten wird ist selten und damit es mit sich selbst so wenn es hält
Wenn Israel Was ist dann passiert wenn dieses Programm hält sie es gar nicht mit der Endlosschleife geändert haben die der es auch nicht mit den Vorschlag des muss hier gelandet sein wenn es selbst muss es hier gelandet sein und 42 ausgegeben habe das heißt aber um gleich 1 gewesen sei
Das heißt dieser Test muss fehlgeschlagen sei dieser ist hier muss gesagt haben wir nicht das Programm Q mit dem Programm Q führte würde hält es nicht wenn das Programm hält lerne ich es muss so gewesen sein dass es nicht hält das haut irgendwie nicht gut sagen es ist schwarz daraus folgt ist es war das kann nicht sein wenn dieses Programm anhält hätte es 42 ausgegeben Ahead gleich 0 sein müssen nicht gleich 1 sein müssen aber gleich nun als aber dass dieser Test wenn ich frage ob das Programm der bekommt Wirkung war ein ob das Programm der Eingabe Q anhält ist der Test gesagt hat das Programm nicht mit anderen Worten Q mit einer Kuh Anwälte ist nicht das Widerspruch Buch das kann nicht sein und sie an was passiert wenn man probiert ok dann es wohl nicht an angenommen ich fühlte mich leq dieses Programm hält nicht ich hier diese Endlosschleifen dann müssen denn sonst recht da also das Letzte was dieses Programm tut was als das letzte was ist dann auf Dauer tot ist die Endlosschleife wenn ist nicht halten für dieses Programm nicht halten würde müsste hier so Schlaraffenland also wäre aber gleich 1 also dieser Test gesagt wenn ich das Programm Q bekommt der Kurei mit Q füttere hält es an der einzige liefert der Test gesagt Q von Kourou hält an keinen von beiden Fällen aus
Herakleides Problemen
Einem logischen Widerspruch dieses Programm Q kann es nicht geben Aus diesen Widerspruch Dieses Programm von kann es nicht so sehr großen Widerspruch produziert Was er sich noch an den Beweis Baumwurzel 2 kamen auch 2 natürlicher Zahlen ist das viel zu lange sei ein hoch zweier natürlicher Zahlen stellt fest auch nicht dass es zu nicht angenommen es gäbe so ein Programm Q stellen sie fest so auch nicht das kann nicht funktioniert zumindest kann es nicht funktionieren wenn ich es selbst bei sich selbst einen gebe es gibt zumindest einen Fall in dem ließ Programme nicht richtig funktionieren kann
Wenn es das Programm Q nicht geben kann die das macht nichts Besonderes das Programm ist das ein ruft anderes Programm auf so Schleife Verzweigung Ausgabe des Programmcodes wirklich fertig billig wenn es das Programm nicht geben kann dann kann es auch das Programm diene nicht das ist das einzige woran scheitern weil es gut nicht hier kann es nicht geben
The war dieser und Übersetzer stark ob ein Programm halt einhält
Mit anderen Worten es gibt keinen solchen universelle Tester der sagen kann ob ein beliebiges Programm
Bei einer beliebigen Eingabe anhält dazu können zumindest einen von konstruieren weil es schief geht
Das zeigt dass dieses Halteproblem dieser ist als man sich so vorstellen kann
Es gibt keinen universelle gestern an neues aber bis vor sofern das Interpretieren Theoretische Informatik eine Notizen zu Interpretation dieses Resultat
Das wird immer so typischerweise verkauft und es gibt keine Chance universell zu dessen der unter der von allgemeinen auch nicht universell ist der Ist er steht des jetzt gebautes müsste gegen die schafft das mal so muss sie sich am 6. Juni komplexer Programme Verarbeitung komplexer Programme verarbeiten die nicht lange nicht die verschachtelte Schleifen das verschachtelte ist Eigentlich immer nur endlich trotzdem aber Von mehr als 10 Millionen ineinander verschachtelt misst verarbeiten muss beliebig komplexe Programme verarbeiten Wenn ich das eigenständige gilt dieses Argument was passiert wenn nicht Mich einschränken Kann man sich fragen was passiert Nur bestimmte Länge erlaubt nur Programm bis ein kB Also ist bestimmte Konstrukte erlaubt sind An einer Stelle erlaubt sind Gern erlaubt sind Und so weiter Was ist das einschränken dass das Programm das die Programme die verarbeitet werden müssen von diesen Test nicht beliebig Kontext endlich dieses Argument zusammen Also da vorsichtig sein und das andere und vor sich sein muss dass dies jetzt gebaut ist muss exakt Resultate wie von Ja oder man musste Aus exaktes Resultat liefern An was passiert wenn man mit 99-prozentiger Wahrscheinlichkeit zufrieden ist durch das Argument schon wieder zusammen Also dieses Argument von verhängt johlend sagten Sie können es verbietet nicht das gestern waren der 99 von 100 Fällen es nicht sagt er würde sich ausschließen was ist mit 99 Prozent Wahrscheinlichkeit zufrieden Ständig ein Programm vor das einfach Mit dem was aber oder kringelt und sagt Vorsicht Wirkung mal nach den Rechtschreibprüfung die Rechtschreibprüfung ist wahrscheinlich sogar nur 90 von 100 Fällen oder das und noch heute 75 von 100 Fällen korrekt und trotzdem ist Rechtschreibprüfung Vielfalt darüber wird sie aber die sagt dieses Argument nicht dieses Argument die nur durch wenn ich verlange dass dieses Programm Pisa-Test 100 Prozent aus der Ferne funktioniert sobald ich das erlaube es ein Prozent nicht funktioniert durch das Argument zusammen und zufrieden ist Auf sie dieses sagen nicht zu streng ein klassisches Resultat am zum Testen von Programmen zum automatischen Testen von Programmen kann nicht automatisch feststellen ob ein Programm einer gegebenen Eingabe anhält oder nicht und geht nicht universelle aber eigentlich ohne das auch nicht und es ist seit das ist doch verdammt schwierig ist allgemein des zuzuschreiben immer das zeigt das 1. zu was komisches passiert das an nichtsdestotrotz glaube das offensichtlich nicht Längenbeschränkungen einbauen hab ich eine Chance wenn ich und andere Werbe-CDs des Beschränkungen ein schon wenig heuristische Verfahren habe die einfach nur typische Fehler Ausblicke auf mit nicht mit 100 Prozent Wahrscheinlichkeit sagen nicht exakt sagen ob ich Probleme haben sondern nur andeuten dass Problem sein könnte dann Haus auch noch also mindestens weitere jenseits bei diesen theoretischen sollte
Länge
YouTube
Natürliche Zahl
Datenbank
Programm
Berechnung
Flussdiagramm
DVD
WINDOWS <Programm>
Komplex <Algebra>
Computeranimation
Richtung
Intel
Datenträger
Informatiker
Halteproblem
VirtualDub
Internet Explorer
Theoretische Informatik
Softwaretest
OpenOffice.org
Interpretierer
Endlichkeit
Constraint <Künstliche Intelligenz>
Heuristik
Computervirus
Zahl
Rechtschreibprüfer
Rechenbuch
Datenverarbeitungssystem
Hypercube
Multi-Tier-Architektur
Verzweigungspunkt
Client
Notepad-Computer
World Wide Web
Tuning
Datei
Firefox <Programm>
Systemverwaltung
Office <Programm>
Prüfprogramm
Programmcode
Virtuelles privates Netzwerk
Variable
Firefox <Programm>
Software
Mathematische Modellierung
Desktop
Informatik
Internet
Programm
Programmiersprache
Mathematik
Datei
Endlicher Automat
Editor
Schnelltaste
Festplatte
Microsoft
Wort <Informatik>

Metadaten

Formale Metadaten

Titel 14.01 Turings Halteproblem
Serientitel Informatik 1, Winter 2010/2011
Autor Loviscach, Jörn
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/9564
Herausgeber Loviscach, Jörn
Erscheinungsjahr 2011
Sprache Deutsch
Produzent Loviscach, Jörn

Inhaltliche Metadaten

Fachgebiet Informatik

Zugehöriges Material

Folgende Ressource ist Begleitmaterial zum Video

Ähnliche Filme

Loading...
Feedback