Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Binäre Kodierung von Turingmaschine
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Binäre Kodierung von Turingmaschine
omar1112
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.02.2010
Mitteilungen: 54
Aus: Palästina(Israel)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2010-02-13


Hallo ,

Ich bin Informatik Student an der FH-Münster, und leide gerade unter der Stress und die Unverständlichkeiten von Theoretische Informatik.

Ich habe eine frage bezüglich die kodierung von Turing maschien:
die Aufgabestelleung lautet folgendes:
Konstruieren sie die Turingmaschine, die bei der Eingabe von ungerader natürlicher Zahl anhält( und sonst nicht!)
geben Sie eine Binäre Kodierung der Maschine an.

mein anstatz :
alle natürliche Ungerade Zahl enden mit den ungeraden Zahlen von  0-9 bzw.{1,3,5,7,9}

hab mir gedacht, die TM soll immer nach rechts gehen, bis das Ende der Zahl erreicht, und dann überprüfen ob der gelesener Zahl einer von die o.g. endliche Menge ist, dann hält sie an, ansonsten nicht!

ist das Richtig? und wie geht die Kodierung!!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46222
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2010-02-13


Hi omar1112,
man kann eine Turing-Maschine binär codieren, das geht immer.
Wie man das aber tun soll, ist keineswegs eindeutig festgelegt, du kommst nicht daran vorbei, dich an die Vorgaben zu halten, die in deinem Skript stehen, und kannst dich ohne weitere Mitteilungen von deiner Seite nicht darauf verlassen, daß wir den Binärstring hinschreiben können oder auch nur erklären können, wie es geht.
Wenn du also an uns die Frage richtest "wie geht die Codierung?", dann kann die so gestellte Frage unmöglich beantwortet werden, denn unsere Rückfrage würde genauso lauten "wie geht die Codierung", und die Antwort (im allgemeinen Fall natürlich, nicht konkret) mußt du selbst geben, anders kommen wir nicht weiter.
Gruß Buri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
omar1112
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.02.2010
Mitteilungen: 54
Aus: Palästina(Israel)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2010-02-13


Hi Buri,

Erstmal vielen Dank für deine schnelle antwort.

die Klausur Theoretische Informatik ist für mich echt der Horror, bin schon 2 mal durchgefallen und jetzt bereite mich auf das dritte Versuch. und Dieses Fach für mich ist das 100% das BAHNHOF Fach der Informatik.

also eine Turing Maschine zu konstruieren ist nicht schwer aber an die Codierung zu kommen ist die frage! aber laut meiner Skript ist eine TM folgendes zu kodieren:
seien {So,...,Sn} = S die Zustände
seien [g0,...,gM} = Γ die Arbeitssymbole
wir ordnen die Anweisung(Si,gj,Si´,gj´,m) das Wort
    ##b(i)#b(j)#b(i´)#b(j´)#b(m)

wobei m=0 , Recht
      m=1 , links
      m=2 , sonst

Nach der Zuordnung ersetzen wir noc 0 mit durch 00, 1 durch 01 und # durch 11 und erhalten eine Binäre Kodierung der Maschine.

meine Lösung für die Aufgabe war folgendes, ich weiss nicht ob es richtig ist:

Die Turing Programm:
0:1:0:1:>
0:2:0:2:>
0:3:0:3:>
0:4:0:4:>
0:5:0:5:>
0:6:0:6:>
0:7:0:7:>
0:8:0:8:>
0:9:0:9:>
0: :1: :<

1:1:1:1:S
1:3:1:3:S
1:5:1:5:S
1:7:1:7:S
1:9:1:9:S

die Codierung: für die erste anweisnug laut Definition:
##b(i)#b(j)#b(i´)#b(j´)#b(m) und 0:1:0:1:>

1111 00 11 01 11 00 11 01 11 00

also ist deiner Meinung dieser Lösungsweg richtig?

danke für die Antwort im Voraus



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46222
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2010-02-13


2010-02-13 17:19 - omar1112 in Beitrag No. 2 schreibt:
also ist deiner Meinung dieser Lösungsweg richtig?
Hi omar1112,
ja, indessen weiß ich nicht, wozu man diese Kreuze # einführt und in die Codierung einbezieht, aber es wird schon einen Grund haben, den ich nur nicht kenne, weil ich nicht die ganzen Zusammenhänge überschaue, aus denen dieses Problem nur ein Ausschnitt ist.
Gruß Buri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
omar1112
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.02.2010
Mitteilungen: 54
Aus: Palästina(Israel)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2010-02-13


Danke Dir Buri zu deine Antworten.. ich werde davon ausgehen dass meine Lösungsweg richtig ist, und hoffe dass sowas nicht in der Kalusur vorkommen wird.

zu den Kreuzen, wir beziehen sie in der codierung damit wir unterscheiden können zwische zustand und gelsenes Zeichen, also so wie ein ",".

ich werde noch paar fragen bezüglich der µ-Operator und das Pumping Lemma, ich werde mich richtig freuen wenn du auf die fragen beantworten kannst!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46222
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2010-02-13


2010-02-13 17:46 - omar1112 in Beitrag No. 4 schreibt:
... ich werde mich richtig freuen wenn du auf die fragen beantworten kannst!
Hi omar1112,
auch ich bin gespannt auf deine Fragen, und freue mich ebenso.
Allerdings habe ich das mit dem Pumping-Lemma noch niemals kapiert (und muß es auch nicht, weil ich keineswegs alles wissen muß oder kann), und über das Pumping-Lemma gibt es mindestens 100 Beiträge in diesem Forum, aber ich habe keine Ahnung davon.
Gruß Buri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1975
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2010-10-23


Hallo zusammen,

noch eine Anmerkung zu der Maschine, die du oben angegeben hast, Omar: Diese Maschine ist richtig. Meist verwendet man allerdings die Konvention, dass die Eingabe einer Turingmaschine nur aus Nullen und Einsen besteht, d.h. man würde eine natürliche Zahl binär (oder sogar unär) kodieren. Damit würde sich das Verfahren, zu testen, ob die Eingabe gerade oder ungerade ist, dann auch darauf beschränken, zu schauen, ob die letzte Ziffer eine 0 oder eine 1 ist, das Programm wäre somit deutlich kürzer.


2010-02-13 17:27 - Buri schreibt: ja, indessen weiß ich nicht, wozu man diese Kreuze # einführt und in die Codierung einbezieht, aber es wird schon einen Grund haben

Den hat es in der Tat. Man möchte ja aus der Codierung das Programm eindeutig wieder zurückerhalten, um damit rechnen zu können. Ohne die Kreuze wäre keineswegs klar, ob das möglich ist, da man die Grenzen einer Programmzeile nicht mehr eindeutig feststellen könnte und die Kodierung möglicherweise nicht injektiv wäre. Daher ersetzt man # ja auch hinterher durch 11 und die anderen Zeichen durch Zahlen, die dafür sorgen, dass nur an den Grenzen von einem COde zum nächsten zwei Einsen nebeneinanderstehen können.

Viele Grüße,
Thorsten

[ Nachricht wurde editiert von Bilbo am 23.10.2010 12:56:33 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
omar1112 wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]