[BuK] Aufgabe 1.3 c.)

[LeeJan]

Hi @ all,

ich habe eine Verständnisfrage an euch, vielleicht könnt Ihr mir ja helfen.
Bin grad bei der Aufgabe 1.3 c.) und habe verstanden das ich eine TM konstruieren soll, die bei Eingabe eines Wortes w mit der Länge k, die aus nur Einsen besteht, die Länge des Wortes um 2^k verlängere...

Habe ich die Aufgabenstellung so richtig verstanden ????

Danke schon mal im Vorraus

Schöne Grüße

[p0llux]

Jo. Du musst quasi den 2-er Logarithmus implementieren. Die denken sich auch nix neues aus :p

EDIT: Omg, dass ist ja echt wie vor 'nem Jahr -.-

[Alexander Urban]

Hehe, das war lustig damals. Im Gegensatz zu dem meisten was danach kam...

(ich hatte einmal ne Aufgabe gelöst, die da lautete "entwickeln sie eine TM"... sogar richtig gelöst. Und hab 3 von 15 Punkten dafür gekriegt, weil ich nur die Übergangsfunktion angegeben hatte und keinerlei Erklärung dazu...)

[Stasik]

als Tipp: das Bandalphabet kann Größer als das Eingabealphabet sein

[Alexander Urban]

War das nicht sogar so, dass das Bandalphabet immer größer ist als das Eingabealphabet, weil es als echte Obermenge desselben definiert ist?

[Stasik]

ja, wegen dem Blank, habe aber noch ein zusätzliches Symbol außer Blank gemeint

[Tempest]

(c) Beschreibe formal eine TM, die die Sprache L entscheidet.

Ich dachte, dass man nur ja/nein sagen muss, ob die Eingabe 2^k lang ist.

Temp

[CrazyPumuckl]

Ja, so verstehe ich die Aufgabe auch. Wobei dann 1= ja, 0 = nein

[philipp]

Korrekt. Aber soo leicht isses gar nicht. Habe dafuer 12 Zustaende benoetigt... (allerdings auch ohne jetzt grossartig zu optimieren)

[CrazyPumuckl]

Wie geht man denn am besten vor? z.B. erstmal alle ungeraden Längen rausfiltern und dann immer das Wort halbieren?

[maddinac]

Ich denke am einfachsten ist es, die Länge des Eingabewortes zu ermitteln und dann zu gucken ob das eine 2erPotenz ist.
So habe ich es jedenfalls gemacht.

[CrazyPumuckl]

ja, das ist doch die aufgabe an sich.

1.) wie zählt man denn bei ner turingmaschine?
2.) wenn man ne anzahl von zeichen ermittelt hat, weiß ich noch immer nicht wie man da feststellt obs ne 2er pot ist.

wenn man doch immer duch 2 teilt, d.h die hälfte der zeichen wegstreicht erhält man - gerade zahlen vorausgesetzt - am ende folgende 2 situationen:

B11B oder B111B. wobei der erste fall bedeutet die zahl ist ne 2er potenz, beim 2ten fall wäre es keine - naja, weiß aber trotzdem nicht so recht wie man das turingisieren soll.

[oxygen]

Mach dir klar, wie "durch 2 teilen" bei einer Binärzahl funktioniert.

[$veno]

Mach dir klar, wie "durch 2 teilen" bei einer Binärzahl funktioniert.

Es geht bei der Aufgabe um Unärzahlen, nicht um Binärzahlen.



CrazyPumuckl: Deine Methode ist exakt richtig, musst sie halt nur inne TM packen.

Gruß Sven

[maddinac]

CrazyPumuckl hat geschrieben:

1.) wie zählt man denn bei ner turingmaschine?
2.) wenn man ne anzahl von zeichen ermittelt hat, weiß ich noch immer nicht wie man da feststellt obs ne 2er pot ist.

1) A 1.3 b)
2) Du hast die Anzahl als Binärzahl