FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

Aufg. 10.1: Mehrband Turing-Maschine

Aufg. 10.1: Mehrband Turing-Maschine 2006-06-15 13:58
MB
ich denke, dass sich alle mehr oder weniger fragen, wie das genau funktionieren soll, auch wenn jantzen das so "halbwegs" erklärte. deshalb eröffne ich mal diesen thread

die fragen die ich mir stelle:
wir haben einen wort
[img]http://mokrates.de/cgi-bin/texstring?%5C(w%20%5Cin%20%5C%7Ba,b%5C%7D%5E*%5C)[/img]
das wird dann ja auf unserem eingabe-band stehen. wir fangen also links auf dem band an mit dem ersten symbol des wortes.
man könnte nun für jedes a oder b eine 1 auf dem entsprechenden der beiden arbeitsbänder eintragen und hinter her die anzahl der 1en der beiden bänder vergleichen. allerdings bleibe ich genau da stecken. wie kann man die arbeitsbänder "vergleichen"?
danke

(ich bin mal wieder genervt von diesem aufgabenblatt!!)

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-15 14:11
Anarch
Wenn du auf Band 1 ne 1 hast, muss auf Band 2 auch ne 1 stehen.
Wenn du auf Band 1 nen # hast, muss auf Band 2 auch nen # stehen, dann fertig.

(Ich hab mal meine Lösung hier gelöscht, es ist nicht sonderlich schwer, und die Übung ist glaube ich ganz nützlich)

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-15 15:12
MB
ok, danke. ich denke ich komme der sache schon näher, vor allem mit hilfe von univ.prof.dr.christoph meinel:
http://www.tele-task.de/player/embedded.php?series=1&language=en&teletask=e9b64947de0749b1590d5590fa44e563&lecture=3

sehr geil, online vorlesung!

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-16 15:10
Anonymer User
Ich hatte die Aufgabe eigentlich so verstanden, dass auf dem Ersten Band die Eingabe ist (also eine Kombination aus A's und B's) und das 2. Band einfach ein Zwischenspeicher ist.

Und man soll dann gucken ob auf dem Ersten Band gleichviele A's wie B's sind. Oder ist das falsch?

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-16 15:24
UncleOwen
Haett ich auch so interpretiert…

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-16 15:31
tilo
Ich denke, die Interpretation ist einem selbst überlassen, oder?
Es geht ja nur darum, zu zeigen, dass die Sprache entscheidbar ist - die Vorgabe, dass man eine Mehrband-TM benutzen soll, ist da wohl eher ne Hilfestellung.

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-16 15:34
Anarch
Und selbst wenn das alles auf Band 1 ist, kann man’s ja kurz auf Band 2 kopieren, oder? ;-)

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-18 09:34
Anonymer User
…die Vorgabe, dass man eine Mehrband-TM benutzen soll, ist da wohl eher ne Hilfestellung.

denke ich eher nicht….

Re: Aufg. 10.1: Mehrband Turing-Maschine 2006-06-18 10:09
Anarch
…die Vorgabe, dass man eine Mehrband-TM benutzen soll, ist da wohl eher ne Hilfestellung.

denke ich eher nicht….

Naja, Mehrband ist ja „trivial“ auf Einband umzubauen, von daher ist es auch mit einem Band kein Problem ;-)