Afg 12.1

[Jack08]

Hi,
hat jemand eine Idee zur 1b? Komme da nicht weiter...

Gruß

[SLS]

Wie mocha schon hier erwähnt hat, könnte man hier einfach von beiden Zahlen solange 1 substrahieren (und das ist relativ einfach) bis mindestens eine davon Null wird. Sobald eine der Zahlen nur wird, kann man sich anhand der anderen Zahl entscheiden, ob für die ursprüngliche Zahlen "kleiner", "gleich" oder "größer" gilt.
Eine (viel effizientere) Alternative ist, die Zahlen bit-by-bit zu vergleichen. Diese Variante ist aber mindestens für mich schwieriger als Turingmachine zu implementieren.
Allerdings als Hinweis zur "wie komplex ist das Ergebnis" - bei mir hat die 1b), implementieret durch Substrahieren, 9 Zustände und auch noch , also insgesamt 12. Ich glaube es ist auch mit weniger möglich, allerdings will man von uns keine optimale Turingmaschine

[CansaSCity]

Ich habe mal eine Frage zur 12.1 a)

Darf man da als Ausgabefunktion g sagen wir mal so:

definieren?

Edit... ich glaube die Antwot habe ich selber gefunden, bitte nur nochmal verifizieren.

Wenn c = (z, b, p) die aktuelle Konfiguration einer Turingma-
schine T ist, dann kann es sein, dass sie einen Schritt durch- Schritt einer
Turingmaschine
führen kann. Das geht genau dann, wenn für das Paar (z, b(p))
aus aktuellem Zustand und aktuell gelesenem Bandsymbol die
Funktionen f, g und m definiert sind. Gegebenenfalls führt das
dann dazu, dass T in die Konfiguration c = (z , b , p ) übergeht,
die wie folgt definiert ist:
• z = f(z, b(p))
falls i = p
b(i)
• ∀i ∈ Z : b (i) =
falls i = p
g(z, b(p))
• p = p + m(z, b(p))

[Script Seite 126]

Des weiteren ist es ja dann notwendig dass X auf die Menge der Ganzen Zahlen Definiert ist... sonst können wir ja nicht jeden Wert auf dem Band darstellen,
oder sollen wir da verschiedene stellen in verschiedenen Feldern anzeigen?
D.h aber dass unser Alphabet unendlich groß ist... ist das bei Touringmaschinen egal?



Danke schon mal

[mfs]

Bei der 12.1b) habe ich folgende Maschine (als Programmcode für http://ironphoenix.org/tril/tm/):

Weil diese Simulation nur einen Haltezustand H kennt, habe ich die 3 verschiedenen Haltezustände durch die Ausgaben E (gleich), G (größer), L (kleiner) gekennzeichnet.

Code: Alles auswählen

1,1,14,1,>
1,0,1,a,>
1,a,1,a,>
1,b,15,b,>
14,1,14,1,>
14,0,14,0,>
14,b,15,b,>
15,1,16,1,<
15,0,15,b,>
15,b,15,b,>
15,_,18,_,<
16,1,2,1
16,0,2,0
16,b,16,b,<
16,a,H,L
2,1,3,0
2,0,2,1,<
2,a,2,a,>
2,b,11,b
3,_,4,_,<
3,1,3,1,>
3,0,3,0,>
3,a,3,a,>
3,b,3,b,>
4,1,5,0
4,0,4,1,<
5,1,5,1,<
5,0,5,0,<
5,a,6,a,>
5,b,5,b,<
6,1,7,1
6,0,6,a,>
6,a,6,a,>
6,b,8,b
7,1,7,1,>
7,0,7,0,>
7,b,8,b,>
8,1,9,1
8,0,8,b,>
8,b,8,b,>
8,_,9,_,<
9,1,9,1,<
9,0,9,0,<
9,a,10,a
9,b,9,b,<
10,1,12,1
10,0,12,0
10,a,10,a,>
10,b,11,b
11,_,H,E
11,1,H,L
11,b,11,b,>
12,1,12,1,>
12,0,12,0,>
12,b,13,b,>
13,_,H,G
13,1,17,1,<
13,0,17,0,<
13,b,13,b,>
17,1,17,1,<
17,0,17,0,<
17,a,1,a,>
17,b,17,b,<
18,1,H,G
18,0,H,G
18,a,H,E
18,b,18,b,<

MfG,
mfs.