Update 3: Korrektur nach Einwand von Phil. Finde ich super, dass Ihr nach fast 3 Jahren immer noch Fehler aufspürt und in den Kommentaren helft, die zu entfernen. Danke! Update 2: Bitte Kommentar von Steve beachten. Grafik habe ich nun ersetzt (Marke 9 hinzugefügt), aber die Punkte für die "Endlosigkeit" der Bänder in den Beispielen […]

In dieser Kurseinheit gibt es zwar nicht viele Lernziele, aber lasst euch nicht täuschen: sie sind wichtig. Die Beiträge zu diesem Thema, die ich auch im passenden Kontext in diesem Beitrag verlinkt habe sind: Primitive Rekursion/LOOP Berechenbarkeit Mue-Rekursion und WHILE/LOOP-Berechenbarkeit Cantorsche Tupelfunktion Starten wir aber einfach wieder anhand der Lernziele und kämpfen uns da durch. […]

Update: Einwand von Felix aufgenommen. Update: Marion hat einen Fehler bei der Berechnung der gefunden. Danke! Update: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz. Update: Hinweis darauf, dass das erste Register bei der Eingabecodierung für eine Maschine belegt werden kann (wir haben keine Einschränkungen), aber nicht durch die Eingabecodierung für eine Registermaschine! […]

Update: Fehler im Automaten behoben. Letzter Beitrag zum Thema... ich tippe besonders langsam, versprochen 😉 Lernziel 5 Was sind determinierte Kellerautomaten? Wir könnten zwar mit nichtdeterministischen Kellerautomaten leben und würden es sogar. Aber es gibt da ein Problem: wir können sie technisch nicht realisieren. Den determinierten Kellerautomaten hatten wir im vorherigen Beitrag auch bereits definiert. Uns […]

Update 2: Einzel- und Mehrschrittrelationen, sowie Überführungsfunktion genauer erklärt. Großes Update: Fehlerbeseitigung und langes Beispiel zum Beweisverfahren Sprache zu Automat(en) zu Grammatik zu Sprache (Lernziel 4). Lernziel 3 Wie sind Kellerautomaten und die von ihnen akzeptierte Sprache definiert? Noch einmal zur Auffrischung: alle Sprachen, die ein endlicher Automat akzeptiert sind regulär. Haben wir aber eine […]