Hi,
hat jemand eine Idee zur 1b? Komme da nicht weiter...
Gruß
Afg 12.1
Re: Afg 12.1
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
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
When we say that two functions are almost always used together, we should remember that "almost" is a euphemism for "not."
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-
- Beiträge: 34
- Registriert: Do 13. Nov 2008, 16:30
Re: Afg 12.1
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.
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
Darf man da als Ausgabefunktion g sagen wir mal so:
definieren?
Edit... ich glaube die Antwot habe ich selber gefunden, bitte nur nochmal verifizieren.
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,
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]
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
Folge dem und du wirst den Weg der Permutation finden
Re: Afg 12.1
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.
MfG,
mfs.
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,<
mfs.