Übungsaufgaben 2

[Christian S.]

Hallo,
Kann bei Aufgabe 18 die Turingmaschine so, wie sie da steht, korrekt sein? Ich bin die a) mehrmals durchgegangen und bei mir "hängt" sich die Turingmaschine immer in Zustand 4 auf ohne jemals in Zustand 2 gewesen zu sein...

Viele Grüße,
Christian

[Patric]

hm erstmal danke hatte bis jetzt immer übersehen das es da noch mehr übungsaufgaben gibt.

Ich bearbeite se mal wenn ich mehr weiß meld ich mich.

Edit: jup die hängt sich echt in 4 immer auf, kann auch irgendwie nicht sein, wenn man irgendwann mal links ein "blank" gelesen hat geht noch weiter nach links ins leere oder man ist zuende...

[Patric]

Aufgabe wurde geändert.

[Christian S.]

Danke. So ganz klar wird mir aber nicht, was die Turingmaschine macht, hat jemand schon die Aufgabe?

Viele Grüße,
Christian

[Patric]

Also das hab ich raus

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

wenn n = m ist stehen am ende n b's auf dem band.
wenn n != m dann stehen |n-m| b's auf dem Band.

n = m folgt ja aus c) und wenn n!=m bekommt man aus a) und b) da wenn man das Prinzip, das man dort entdeckt, verfolgt ist irgendwann n = m. Musste bissle rum probieren, ist bissle komisch ne total sinnfreie TM zu haben -.-.

Aber kann auch sein das ich mich Irre, wenn man da ewig rumprobiert bekommt verliert man den überblick

[Christian S.]

Habe jetzt

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

b^(m-|max(n, m) - |n - m||)

Probiere mal mit deiner Lösung abbb und bbba durch in der TM.

[Patric]

hm stimmt meins passt da nich so ganz -.-

du meintest schon aaab statt bbba oder?

[Christian S.]

hm stimmt meins passt da nich so ganz -.-

du meintest schon aaab statt bbba oder?

Genau, ja klar, Buchstabendreher .

[Patric]

Hab jetzt ne Lösung die auch ziemlich schön ist wie ich finde:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

b^ggt(n,m) , steht am Ende auf dem Band. Das ganze Funktioniert mit euklidischem Algorithmus wie ich das seh, immer wenn z4->z0 bzw z2->z0 passier ist wieder ein schritt abgeschlossen.

[Romeo]

Hallo,

Wenn das jemandem hilft: Ich kann mich nur anschließen!

Allerdings habe ich für die einzelnen Fälle:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

n = m: am Ende beim Zustand f b^n = b^m
n < m: am Ende des Zyklus a^n b^(m-n)
m < n: am Ende des Zyklus a^(n-m) b^m

Dann passt das auch mit dem euklidischen Algorithmus.

Schöne Grüße
Roland