{"id":754,"date":"2012-11-04T17:31:30","date_gmt":"2012-11-04T15:31:30","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=754"},"modified":"2025-11-25T22:56:36","modified_gmt":"2025-11-25T21:56:36","slug":"ti-turing-maschinen-und-wortfunktionen","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=754","title":{"rendered":"TIA: Turing-Maschinen, Hilfssymbole (Lernziele KE3, Update 3)"},"content":{"rendered":"

Update 3<\/strong>: Nach Olivers Einwand (Danke hier nochmal!) habe ich den Abschnitt \u00fcber Hilfssymbole erneut \u00fcberarbeitet.<\/p>\n

Update 2<\/strong>: Wow, beim Durchgehen des Eintrags sind mir massive Schnitzer bei den Hilfssymbolen aufgefallen. Hoffentlich sind die jetzt raus. Sorry!<\/p>\n

Update<\/strong>: mit dem Eintrag sollten nun alle Lernziele aus KE3 erschlagen worden sein. Ist zwar etwas lang geworden, aber vielleicht hilft es dem ein oder anderen beim Verst\u00e4ndnis. Die neuen Erkenntnisse z.B. bzgl. der Hilfssymbole entstammen dem Mentoriat in Hagen mit Herr Dr. Halbach. Ich kann nur ausdr\u00fccklich raten diese Mentoriate in Anspruch zu nehmen und auch immer Fragen zu stellen wenn einem etwas nicht klar sein sollte.<\/p>\n

Habe bei vielen Mentoriaten gesehen, dass die Leute auf die fragenden Blicke des Mentors 2 Stunden lang immer nur flei\u00dfig nicken. Nach dem Mentoriat schaut man trotzdem in die gleichen, ratlosen Gesichter ein st\u00fcckweit mehr resignierter Komillitonen. Also fragen bis es „Klick!“ macht. Auch sind viele Mitstudenten gerne bereit es einem auch mit anderen Worten zu erl\u00e4utern. Nur keine Scheu, sitzen doch alle im selben Boot \ud83d\ude09<\/p>\n

Einleitung<\/h2>\n

Aber fangen wir an: w\u00e4hrend in der Literatur zun\u00e4chst Einband-Maschinen eingef\u00fchrt werden um sie dann durch Mehrbandmaschinen zu ersetzen wird das in dem Kurs an der FU hier genau anders rum gemacht (wie vieles andere im Skript auch…). Auch werden die Turing-Maschinen oft als 7-Tupel definiert, im Skript haben wir ein 5-Tupel. Solche Dinge machen es – meiner Meinung nach – dem Leser unn\u00f6tig schwer sich den sehr wichtigen Stoff zu erarbeiten.<\/p>\n

Anstatt dass man vielleicht in Zusatzliteratur einen Sachverhalt in anderen Worten verst\u00e4ndlicher nachlesen kann, muss man die Definitionen erst in die Definitionen des Skripts \u00fcberf\u00fchren. Daf\u00fcr muss man aber zuerst verstehen, was im Skript denn steht. Hierf\u00fcr hat man sich aber speziell die Zusatzliteratur besorgt. Da bei\u00dft sich die Katze in den Schwanz.<\/p>\n

Ich m\u00f6chte hier versuchen bei der Definition des Skripts zu bleiben und die Parallelen zur „\u00fcblichen“ Definition zu ziehen damit man auch mit Fremdliteratur arbeiten kann.\u00a0Ebenso w\u00fcrde ich auch lieber mit Einbandmaschinen starten, statt wie im Skript sofort Mehrbandmaschinen einzuf\u00fchren um diese dann durch Einbandmaschinen zu ersetzen…<\/p>\n

Darstellungsweise:<\/strong> Zun\u00e4chst jedoch zur Darstellungsweise. Am h\u00e4ufigsten wird die un\u00e4re Darstellungsweise f\u00fcr Turingmaschinen verwendet, d.h. eine 5 auf dem Eingabe- oder Ausgabeband besteht aus f\u00fcnf Einsen \\((11111)\\). Die bin\u00e4re Darstellung ist zwar etwas h\u00fcbscher und in einigen Bereichen durchaus sinnvoll, aber die Formulierung von Algorithmen ist mit der un\u00e4ren Darstellungsweise meist einfacher.<\/p>\n

Einbandmaschinen<\/h2>\n

Im Gegensatz zu Mehrbandmaschinen besitzt diese nur ein einziges Band, welches als Ein- und Ausgabe- sowie Arbeitsband dient. Die Eingabeworte befinden sich hier zu Beginn rechts von Lesekopf und sind nur Trennzeichen getrennt. Links befindet sich die Ausgabe. W\u00e4hrend der Berechnung wird die Eingabe dann durch die Ausgabe ersetzt, d.h. gel\u00f6scht. Am Ende steht das Ergebnis links vom Kopf.<\/p>\n

\"\"<\/a><\/p><\/blockquote>\n

Im Skript sind die Einbandmaschinen definiert als:<\/p>\n

\\(M=(F,(\\Sigma^*)^k,\\Sigma^*,EC^{(k)},AC)\\)<\/p>\n

Wir erkl\u00e4ren den Spa\u00df hier einfach mal:<\/p>\n