STP063: Fleißige Biber

Wie auch schon in der Vergangenheit nehmen wir es mit der Aktualität unserer "Berichterstattung" nicht ganz so genau. Und so liegt das entsprechende Ereignis etwa 2¹/₂ Monate in der Vergangenheit. Der fünfte fleißige Biber wurde gefunden.ShownotesWir haben Feedback bekommen, siehe unten. Zuerst die Shownotes zum eigentlichen Thema: aktueller Anlass: Der fünfte fleißige Biber wurde gefunden Rückbezug zu STP000: theoretische Informatik ist ein Teilgebiet der Mathematik, dass Xyrill lieber "Berechnungstheorie" nennen würde hierin insbesondere "Berechenbarkeitstheorie": Welche Probleme lassen sich mit Rechenmaschinen lösen? Church-Turing-These: Berechenbarkeit ist eine intrinsische Eigenschaft eines Problems und nicht abhängig davon, welchen Computer ich zur Lösung einsetze "Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein." Analyse der Berechenbarkeit eines Problems anhand von einfachen Modellmaschinen, z.B. der Turing-Maschine (daher "Turing-berechenbar") Turing-Vollständigkeit: die Eigenschaft einer Rechenmaschine, alle Probleme lösen zu können, die auch eine Turing-Maschine lösen kann (mal abgesehen von weltlichen Einschränkungen wie Speicherplatz und Rechenzeit) Rückbezug zu STP021 (Reguläre Ausdrücke): dort hatten wir stärker limitierte Maschinenmodelle erwähnt (endliche Zustandsautomaten, Kellerautomaten) Aufbau einer Turing-Maschine (Beispielbild aus Wikipedia) unendlich langes Speicherband mit Feldern, auf denen entweder 0 oder 1 stehen kann Lese-/Schreibkopf, der das aktuelle Feld lesen und schreiben kann sowie sich in Einzelschritten entlang des Bandes bewegen kann Programm: endliche Menge von Zuständen, und eine Zustandsübergangsfunktion, die auf Basis der gelesenen Zeichen entscheidet und Zeichen überschreibt sowie den Lesekopf bewegt Xyrill hat ein Beispiel mitgebracht: ein Programm, dass zwei positive Ganzzahlen subtrahiert; die Zahlen sind als Folgen von 1 gegeben, getrennt von einer 0; zum Beispiel "3-2" wird eingegeben als "111011" und der Lesekopf startet am Anfang der ersten Zahl Warnung: Wir haben während der Aufzeichnung bemerkt, dass diese Maschine inkorrekt ist. Damit keine Verwirrung entsteht, haben wir die Notizen nicht angepasst. Zustandsvorrat (durchbuchstabiert