Turing-Maschine < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 So 10.12.2006 | | Autor: | Phoney |
| Aufgabe | Schreiben Sie ein TM-Programm, welches auf ein leeres Band (...###...) möglichst viele 1en schreibt und danach hält. Die TM darf maximal 4 verschiedene Zustände + Haltezustand haben.
Ihr Programm muss mindestens fünf 1en auf das Band schreiben und danach halten.
Stellen Sie nebenbei noch eine Formel auf, die angibt, wie viele verschiedene TMs mit n Zuständen und einem Bandalphabet mit m Zeichen es gibt. |
Hallo.
Also erst einmal zu der Übungsaufgabe mit dem Band. Wieso soll es da nur fünf Einsen geben und nicht die Länge der Zeichen auf dem Band?
Ich meine, der Zeiger steht auf #. Da soll er eine 1 schreiben und nach rechts gehen. Trifft er wieder auf eine #, soll er wieder eine 1 schreiben. So lange, bis das Band zu Ende ist. War das Band nicht unendlich lang?
Oder soll er eine 1 schreiben und dann nach rechts gehen (in Zustand 2)
Dann trifft er wieder auf ein # und soll eine 1 schreiben, nach links gehen (Zustand 3). Er trifft auf eine 1, schreibt eine 1, geht nach links, trifft auf # (da das Band ja leer ist), er schreibt eine 1 und geht nach rechts (Zustand 4). Dort trifft er auf eine 1, geht nach rechts, solange er auf eine 1 trifft. Wenn er auf # kommt, schreibt er eine 1 und wechselt in den Zustand 3 (also wieder nach links gehen)...
Dann komme ich aber trotzdem auf unendlich viele Einsen?
Und wie soll man dazu eine Formel aufstellen? Ich verstehe auch nicht, was die Formel mit der Aufgabe zu tun haben soll.
Viele Grüße von
Johann
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:30 Mo 11.12.2006 | | Autor: | Frank05 |
> Also erst einmal zu der Übungsaufgabe mit dem Band. Wieso
> soll es da nur fünf Einsen geben und nicht die Länge der
> Zeichen auf dem Band?
Weil die Turing-Maschine nach getaner Arbeit auch anhalten soll (sprich in einen Endzustand gehen soll). Ohne diese Einschränkung hast du recht, dass es trivial wäre.
> Ich meine, der Zeiger steht auf #. Da soll er eine 1
> schreiben und nach rechts gehen. Trifft er wieder auf eine
> #, soll er wieder eine 1 schreiben. So lange, bis das Band
> zu Ende ist. War das Band nicht unendlich lang?
Ja ist es und das wird auch dein Problem sein, wenn du die richtige Lösung mit Terminierung suchst.
> Oder soll er eine 1 schreiben und dann nach rechts gehen
> (in Zustand 2)
> Dann trifft er wieder auf ein # und soll eine 1 schreiben,
> nach links gehen (Zustand 3). Er trifft auf eine 1,
> schreibt eine 1, geht nach links, trifft auf # (da das Band
> ja leer ist), er schreibt eine 1 und geht nach rechts
> (Zustand 4). Dort trifft er auf eine 1, geht nach rechts,
> solange er auf eine 1 trifft. Wenn er auf # kommt, schreibt
> er eine 1 und wechselt in den Zustand 3 (also wieder nach
> links gehen)...
>
> Dann komme ich aber trotzdem auf unendlich viele Einsen?
Und die TM geht auch nie in einen Endzustand.
> Und wie soll man dazu eine Formel aufstellen? Ich verstehe
> auch nicht, was die Formel mit der Aufgabe zu tun haben
> soll.
Sie gibt dir eine obere Schranke. Falls du nicht herausbekommst, wie die TM aussehen musst kannst du dir damit überlegen wieviele mögliche TMs du dir theoretisch ansehen müsstest um festzustellen, welche davon die Aufgabe erfüllt.
Hier noch etwas 'Literatur' zu deiner Aufgabe: http://de.wikipedia.org/wiki/Busy_Beaver
|
|
|
|
