Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
108. Video Theoretische Informatik WS 13/14 - Einführung in das Halteproblem - unistreams
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 13 Zeilen
- uns interessiert eigentlich diese Frage ist das sogenannte allgemeine halteproblem ich habe eine
- Binde beliebige touringmaschine ich habe ein beliebiges Wort was ich dieser touringmaschine als Eingabe gebe und mich interessiert die Frage hält das
- Ding in an oder hält es nicht an also ich wende dann die touringmaschine oder den Algorithmus m habe ich den hier genannt
- wenn ich auf die Eingabe an ja und ist das sozusagen eine entscheidbares Problem das ist eine Frage die kann ich so formulieren ich
- muss ihn Entscheidung fällen entweder ja oder nein können wir das lösen
- und die Aussage wird sein wir können es nicht lösen ich hätte das glaube ich glaube ich schon mal gefragt was ich dann
- auch ganz gerne in so einer mündlichen Prüfung immer mal Frage im ersten Semester da lernen Sie Programmierung ja da kriegen sie
- irgendwie eine Fragestellung ein Problem quasi eine problemspezifikation sie sollen Programm dafür schreiben ja und sozusagen
- Algorithmus der auf der einen Seite ihr Computerprogramm nimmt was Sie geschrieben haben auf der anderen Seite die Spezifikation nimmt und guckt ob es
- erstmal überhaupt anhält für jede mögliche Eingabe und B ob es die gewünschte Spezifikation erfüllt bei einer unendlich großen Mengen von
- Eingaben also alles andere ist uninteressant wenn ich nur irgendwie endlich viele Probleme endlich viele Möglichkeiten
- haben das hat man schon gesagt das können wir immer entscheiden und dann bauen wir irgendwie Automaten der das Fest verdratet hat aber wenn ich
- unendlich viele Eingaben habe dann kann ich sowas nicht automatisiert überprüfen und warum das so ist das wollen wir uns noch überlegen
Zum Nachlesen
HalteproblemDas Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt …
Universelle TuringmaschineEine universelle Turingmaschine (UTM) ist in der Informatik eine Turingmaschine, die eine beliebige Turingmaschine auf beliebiger Eingabe simuliert.
TuringmaschineEine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …
DiagonalspracheDie Diagonalsprache ist die zentrale Konstruktion im Beweis der Unentscheidbarkeit des Halteproblems. Die Konstruktion der Sprache basiert auf dem Prinzip der …