108. Video Theoretische Informatik WS 13/14 - Einführung in das Halteproblem - unistreams
Unistreams
https://www.youtube.com/watch?v=waserxYHqxc

Transkript (automatisch erstellt)

0:05 uns interessiert eigentlich diese Frage ist das sogenannte allgemeine halteproblem ich habe eine
0:14 Binde beliebige touringmaschine ich habe ein beliebiges Wort was ich dieser touringmaschine als Eingabe gebe und mich interessiert die Frage hält das
0:22 Ding in an oder hält es nicht an also ich wende dann die touringmaschine oder den Algorithmus m habe ich den hier genannt
0:29 wenn ich auf die Eingabe an ja und ist das sozusagen eine entscheidbares Problem das ist eine Frage die kann ich so formulieren ich
0:39 muss ihn Entscheidung fällen entweder ja oder nein können wir das lösen
0:46 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
0:54 auch ganz gerne in so einer mündlichen Prüfung immer mal Frage im ersten Semester da lernen Sie Programmierung ja da kriegen sie
1:02 irgendwie eine Fragestellung ein Problem quasi eine problemspezifikation sie sollen Programm dafür schreiben ja und sozusagen
1:10 Algorithmus der auf der einen Seite ihr Computerprogramm nimmt was Sie geschrieben haben auf der anderen Seite die Spezifikation nimmt und guckt ob es
1:19 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
1:26 Eingaben also alles andere ist uninteressant wenn ich nur irgendwie endlich viele Probleme endlich viele Möglichkeiten
1:33 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
1:40 unendlich viele Eingaben habe dann kann ich sowas nicht automatisiert überprüfen und warum das so ist das wollen wir uns noch überlegen