Berechenbare Funktionen: Unärsystem, n + 1, n − 1 – Berechenbarkeit und ihre Grenzen

Rechnen mit der Turingmaschine

Bisher hat die Maschine Zeichen umgeschrieben. Jetzt soll sie rechnen, und zwar mit natürlichen Zahlen im Unärsystem („Bierdeckelsystem“): Die Zahl n steht als n Einsen auf dem Band, wie Striche auf einem Bierdeckel. Die Zahl 0 ist das leere Band.

Merke: Zahlen auf dem Band

Eine natürliche Zahl n steht als n aufeinanderfolgende Einsen auf dem Band.
Mehrere Zahlen trennt eine 0.
Der Kopf steht zu Beginn und am Ende unter dem rechtesten Zeichen.

Lückentext

Stelle die Zahlen im Unärsystem dar. Die Zahl 4: Die Zahl 9:

Strategie: erst Anfang und Ende

Bevor du eine Maschine entwirfst, beschreibe die Aufgabe: Wie sieht das Band zu Beginn aus, wie am Ende, und wo steht der Kopf? Danach überlegst du den Weg dorthin. Auch die Sonderfälle am Rand gehören dazu.

Lückentext

Die Maschine soll zu einer Zahl 1 addieren. Steht zu Beginn die Zahl 4 auf dem Band, stehen am Ende Einsen darauf. Bei der Zahl 9 sind es Einsen.

add1

Aufgabe 1: Erstelle eine Maschine add1: Auf dem Band steht eine Zahl n ≥ 1 im Unärsystem. Am Ende soll n + 1 auf dem Band stehen.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

sub1

Aufgabe 2: Erstelle eine Maschine sub1: Auf dem Band steht eine Zahl n ≥ 1 im Unärsystem. Am Ende soll n − 1 auf dem Band stehen.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

Freitext

Wende deine Maschine sub1 mehrmals hintereinander an: Stelle die Zahl 3 ein, führe sie aus und klicke danach immer wieder auf „Nochmal ausführen“. Was geschieht, und was folgt daraus für die Zahl 0?

💡 Zum Speichern deiner Antwort bitte einloggen.

Berechenbar heißt: Es gibt eine Maschine

Merke: Turingmaschinen-berechenbar

Eine Funktion f, die Symbolfolgen neue Symbolfolgen zuordnet, heißt Turingmaschinen-berechenbar, wenn es eine Turingmaschine T gibt, die für jede Eingabe w hält und f(w) auf dem Band erzeugt:

Zu Beginn steht w auf dem Band und der Kopf unter dem Anfang der Symbolfolge.
Am Ende hält T und hat f(w) auf das Band geschrieben.

Merke: Church-Turing-These

Eine Funktion ist im intuitiven Sinn berechenbar genau dann, wenn sie Turingmaschinen-berechenbar ist. Jede Funktion, die ein Algorithmus berechnen kann, kann also auch eine Turingmaschine berechnen.

Das ist eine These, kein Satz: Man kann sie nicht beweisen, weil „intuitiv berechenbar“ nicht formal definiert ist.

Freitext

Die Funktion add1 ordnet jeder Zahl n die Zahl n + 1 zu. Ist add1 Turingmaschinen-berechenbar? Begründe.

💡 Zum Speichern deiner Antwort bitte einloggen.

✏️ Übungen zu diesem Kapitel

3 freiwillige Aufgaben zum Üben und Weiterdenken.

Zu den Übungen →