[S] Turingmaschinen Übungen

[Quantar]

Ahoi, grade mit Erfolg mein erstes Programm geschrieben und Lust auf mehr bekommen. Weiß jemand wo es da weitere Aufgaben gibt a la "Schreiben sie ein Programm welches dieses und jenes macht". Sollte nur (noch) nicht zu komplex sein.

gruß
Q

[AlSvartr]

1. Turingmaschine, die die Sprache L={a^nb^nc^n|n>=0} akzeptiert
2. Turingmaschine, die a+b mit a,b aus den natürlichen Zahlen berechnet (Eingabecodierung durch Bierdeckelnotation ;))

[Quantar]

Das mit der Bierdeckelnotation habe ich nicht so recht verstanden. Unärer Code :confused:
Ist damit gemeint: 1=1, 11=2, 111=3, 1111=4 etc?

[derpinguin]

Genau. Das Unärsystem besitzt nur ein Zeichen.

[AlSvartr]

Ne ganz nette Aufgabe ist auch noch, allgemein den Aufbau einer linear beschränkten Turingmaschine anzugeben, die genau die Sprache einer beliebigen kontextsensitiven Grammatik akzeptiert. Also halt zeigen, dass linear beschränkte Turingmaschinen mindestens so mächtig sind wie kontextsensitive Grammatiken (umgekehrt gehts natürlich auch, sind ja äquivalent).

[Nasenbaer]

Naja ne TM ist nur ein theoretisches Modell und sicher nicht dazu gedacht "komplexere" Progamme zu entwickeln.
Falls du gerade beim Grundstudium damit in Berührung gekommen bist würde ich in sowas nicht zuuuviel Zeit in sowas investieren und mich lieber mit den theoretischen und beweistechnischen Möglichkeiten, die TMs ermöglichen beschäftigen. Also wichtigen Sätzen und ihren Beweisen, die ja meist eine TM bemühen. Sowas ist in Prüfungen sicher wichtiger.

Aber die ein oder andere Übung schadet sicher nicht. :)

[Quantar]

Ne ganz nette Aufgabe ist auch noch, allgemein den Aufbau einer linear beschränkten Turingmaschine anzugeben, die genau die Sprache einer beliebigen kontextsensitiven Grammatik akzeptiert. Also halt zeigen, dass linear beschränkte Turingmaschinen mindestens so mächtig sind wie kontextsensitive Grammatiken (umgekehrt gehts natürlich auch, sind ja äquivalent).
Ich glaub da muss ich noch ein paar Wochen warten bis Chomsky dran ist. Der müsste mir da noch die ein oder andere Begrifflichkeit für liegern :redface:

Falls du gerade beim Grundstudium damit in Berührung gekommen bist würde ich in sowas nicht zuuuviel Zeit in sowas investieren und mich lieber mit den theoretischen und beweistechnischen Möglichkeiten, die TMs ermöglichen beschäftigen. Also wichtigen Sätzen und ihren Beweisen, die ja meist eine TM bemühen.
Nun ja, ich studiere derzeit noch Philosophie und vieles wird -leider- nur sehr rudimentär behandelt. Aber da ich mich im nächsten Studium mit TI rumschlagen muss will ich mich jetzt schon so gut mit der Materie beschäftigen wie es nur geht.
Zudem muss ich sagen, nachdem ich mich ein paar Tagen mit beschäftigt habe, werden mir einige Probleme wie Entscheidbarkeit/Halteproblem überhaupt richtig bewusst.
Ansonsten finde ich alleine den Gedanken einer Universalmaschine schon faszinierend genug :D

[Nasenbaer]

Nun ja, ich studiere derzeit noch Philosophie und vieles wird -leider- nur sehr rudimentär behandelt. Aber da ich mich im nächsten Studium mit TI rumschlagen muss will ich mich jetzt schon so gut mit der Materie beschäftigen wie es nur geht.
Zudem muss ich sagen, nachdem ich mich ein paar Tagen mit beschäftigt habe, werden mir einige Probleme wie Entscheidbarkeit/Halteproblem überhaupt richtig bewusst.
Ansonsten finde ich alleine den Gedanken einer Universalmaschine schon faszinierend genug :D
Naja ich hab ja schon gehört, dass es Leute gibt, die theoretische Informatik toll finden aber hab das immer für ein Gerücht gehalten. *gg*

Kannst dir ja mal SAT anschauen oder noch besser den Satz von Rice. Letzteren hab ich bis heute nicht verstanden aber die beiden bemühen auch eine TM zum Beweis und ich denke, wenn man die verstanden hat, dann hat man bzgl. Handhabung von TMs und theoretischen Grundlagen schonmal ordentlich was drauf.

[Quantar]

Ich hätte nochmal ne Frage.
ich wanke gerade die "Berechenbarkeit" eindeutig von der "Entscheidbarkeit" abzugrenzen.
Berechenbar bedeutet ja, dass es einen Weg/Algorithmus/Methode gibt, um bei einer beliebigen
Eingabe die entsprechende Ausgabe berechnen zu können. Dies ist natürlich ziemlich weitläufig.
Die Entscheidbarkeit ist die "Berechenbarkeit" von Mengen/Sprachen. Jetzt fällt es mir schwer
zu verstehen, was denn nun noch alles bleibt respektive was denn alles an Eingaben nicht als Menge/Sprache
aufzufassen ist.

[Nasenbaer]

Ich hätte nochmal ne Frage.
ich wanke gerade die "Berechenbarkeit" eindeutig von der "Entscheidbarkeit" abzugrenzen.
Berechenbar bedeutet ja, dass es einen Weg/Algorithmus/Methode gibt, um bei einer beliebigen
Eingabe die entsprechende Ausgabe berechnen zu können. Dies ist natürlich ziemlich weitläufig.
Die Entscheidbarkeit ist die "Berechenbarkeit" von Mengen/Sprachen. Jetzt fällt es mir schwer
zu verstehen, was denn nun noch alles bleibt respektive was denn alles an Eingaben nicht als Menge/Sprache
aufzufassen ist.
Wikipedia ist super in Sachen TI aus meiner Sicht. Schau da mal nach, da ist es meist sehr exakt definiert aber auch gut verstandlich find ich. Ich würd da jetzt auch nur abschreiben um das zu erklären. :D

[Aen-Die]

1. Turingmaschine, die die Sprache L={a^nb^nc^n|n>=0} akzeptiert
2. Turingmaschine, die a+b mit a,b aus den natürlichen Zahlen berechnet (Eingabecodierung durch Bierdeckelnotation ;))

*g* Sieht nach ner aufgabe von unserem Herrn Witt aus :biggrin: Wußte gar nicht, dass leute von unserer FH auch hier vertreten sind

[Nasenbaer]

*g* Sieht nach ner aufgabe von unserem Herrn Witt aus :biggrin: Wußte gar nicht, dass leute von unserer FH auch hier vertreten sind
Also ich komm von der UNI Rostock und kenn die Beispiele auch. Sind so typische Standardbeispiele, die wohl so ziemlich jeder Prof. mal erwähnt.

[Quantar]

Wikipedia ist super in Sachen TI aus meiner Sicht. Schau da mal nach, da ist es meist sehr exakt definiert aber auch gut verstandlich find ich. Ich würd da jetzt auch nur abschreiben um das zu erklären. :D
Nun, bei Wiki steht es ebenso, daher das Unverständnis ;)

Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit, welcher eingefuehrt wurde um die "Berechenbarkeit" von Mengen (d. h. von Sprachen) anzugeben, die dann aber eben nicht "Berechenbarkeit" sondern "Entscheidbarkeit" genannt wird.

Ich hab ja auch viel mit formaler Logik zu tun -in einem philosophischen Kontext eben-. Jetzt sehe ich eine Aussage X, und weiß, dass ich sie beweisen/ableiten kann. Ist X jetzt berechenbar oder entscheidbar? :confused:

[Nasenbaer]

Ok dann versuch ichs mal zu erklären:

Entscheidbarkeit:
Eine Menge ist entscheidbar (rekursiv aufzählbar), genau dann wenn eine berechenbare Funktion existiert, die Zu einer beliebgien Eingabe, nach endlicher Zeit sagen kann, ob die Eingabe (z.B. ein Wort einer Sprache) zu dieser Menge gehört oder nicht.
Wichtig ist, dass die Funktion auch sagen kann, wenn ein Element nicht zur Menge gehört.

Oder in einfach: Die Funktion sagt definitiv irgendwann "Element gehört dazu" oder "Element gehört nicht dazu"

Semi-Entscheidbarkeit:
Eine Menge ist semi-entscheidbar (aufzählbar), genau dann wenn eine berechnbare Funktion existiert die nach endlicher Zeit sagen kann ob eine Element zur Menge gehört. Die Berecnung bicht im Allgemeinen nicht ab, wenn das Element nicht zur MEnge gehört.
Salop heißt das, dass die Fkt. sagen kann "das Element gehört dazu" oder "ich weiß nicht ob es dazugehört also lass mich noch weiter rechnen, vielleicht bekomm ich das doch noch raus" *g*


Berechnenbarkeit:
Eine Funktion ist berechnbar, wenn es eien Algorithmus gibt, der zur Eingabe x nach endlicher Zeit f(x) berechnet, falls f() für die Eingabe x definiert ist.

Die Chruch'sche These:
Alle im intutiven Sinne berechenbaren Funktionen, sind genau die Funktionen die mittels Turingmaschine berechenbar sind.

Man nimmt an, dass die These gilt, da aber "intuitiv" informal ist, kann mans nicht beweisen. Mit anderen Worten, man hat bisher keine klar definierte Funktion gefunden, die man nicht auch mit einem Computer berechnen kann.


Manchmal kommt dann die Meinung: "Na dann gibt mal nen Algorithmus an der bei jeder Eingabe irgendwas ausgibt, also ne Zufallsfunktion". Diese Arbeitsweise ist natürlich nicht klar definiert und somit ein blödes Argument. *g*

[Quantar]

ah ok, so langsam lichtet es sich =)
Entscheidbarkeit gibt also lediglich ein true/false aus. Ich frage zb ob X ein Element der Menge der Primzahlen ist und bekomme nach einer endlichen ein [true] oder [false] geliefert.

Dann müssten formale Aussagen/Sätze doch auch in diesen Bereich fallen respektive der Ableitungs(Beweis)begriff.
Man beweist(=true) oder widerlegt(=false) eine Aussage.

Berechenbarkeit gibt einen Funktionswert aus. (Wobei ich mich frage ob man einen Wahrheitswert nicht auch irgendwie berechnen kann :confused:).

[Nasenbaer]

Berechenbarkeit gibt einen Funktionswert aus. (Wobei ich mich frage ob man einen Wahrheitswert nicht auch irgendwie berechnen kann :confused:).
Nein Berechenbarkeit sagt aus, ob etwas berechnet werden kann. Also nur bekomme ich auf eine Frage eine Antwort oder ist es unmöglich die Antwort jemals zu berechnen. Die Antwort selbst kann kann true/false/100/345,3456/Hallo/bitte/danke sein. Es giht nur darum ob du ne Funktion schreiben kanns in Java z.B. die dir sowas ausrechnet oder nicht. Wenn berechenbar, dann kannst du die Funktion in Java schreiben, wenn nicht dann kannst du sie weder in Java noch C++ oder als Turingmaschine formulieren.

[Quantar]

Hmm, aber müsste es im Zweifelsfall nicht heißen, dass etwas noch nicht berechenbar ist? Berechenbarkeit kann man beweisen, Unberechenbarkeit doch wohl kaum. Gibt es denn ein Beispiel etwas unberechenbares was ein nicht Mathematiker versteht? =)

[Nasenbaer]

Hmm, aber müsste es im Zweifelsfall nicht heißen, dass etwas noch nicht berechenbar ist? Berechenbarkeit kann man beweisen, Unberechenbarkeit doch wohl kaum. Gibt es denn ein Beispiel etwas unberechenbares was ein nicht Mathematiker versteht? =)
Das ist ja die Chruch'sche These:
Alle im intuitiven Sinne berechenbaren Funktionen sind gerade die turingberechenbaren Funktionen.

D.h. sobald du eine mathmatische Funktion angeben kann, die mathematisch korrekt definiert ist, dann kannst du sie auch mit Computern berechnen.

Es mag natürlich Probleme geben, die man nicht einmal mathematisch beschreiben kan oder noch nicht kann aber dann sind sie auch nicht "intuitiv berechenbar". :)
z.B. Eine Funktion f(Zeitpunkt,Ort) = Folgen, die dir bei gegebenen Zeitpunkt und bekannten Ort an dem du bei rot über die Ampel gehst und die dir dann die Folgen berechenet, die das auf das gesamte Universum haben wird. Wie diese Funktion das Tupel (Zeitpunkt,Ort) auf eine Folgenmenge abbilden kann, kann dir auch kein Mathematiker sagen, weil man die ganzen Zusammenhänge gar nicht kennen kann.
Ist natürlich wieder sehr weit hergeholt, denn wüsste man über die Zusammenhänge bescheid, wäre es sicher theoretisch berechenbar nur nicht praktisch - wenn man dann alle Teilchen des Universum simulieren will reicht dein RAM wohl nicht ganz aus. :D

Berechenbarkeit kannst du beweisen indem du einfach einen Algorithmus angibst, also ein C-Programm oder eine Turingmaschine etc.

[AlSvartr]

*g* Sieht nach ner aufgabe von unserem Herrn Witt aus :biggrin: Wußte gar nicht, dass leute von unserer FH auch hier vertreten sind
Erwischt ;) ... kennen wir uns? ;)

[Quantar]

Das ist ja die Chruch'sche These:
Alle im intuitiven Sinne berechenbaren Funktionen sind gerade die turingberechenbaren Funktionen.

D.h. sobald du eine mathmatische Funktion angeben kann, die mathematisch korrekt definiert ist, dann kannst du sie auch mit Computern berechnen.

Es mag natürlich Probleme geben, die man nicht einmal mathematisch beschreiben kan oder noch nicht kann aber dann sind sie auch nicht "intuitiv berechenbar". :)
z.B. Eine Funktion f(Zeitpunkt,Ort) = Folgen, die dir bei gegebenen Zeitpunkt und bekannten Ort an dem du bei rot über die Ampel gehst und die dir dann die Folgen berechenet, die das auf das gesamte Universum haben wird. Wie diese Funktion das Tupel (Zeitpunkt,Ort) auf eine Folgenmenge abbilden kann, kann dir auch kein Mathematiker sagen, weil man die ganzen Zusammenhänge gar nicht kennen kann.
Ist natürlich wieder sehr weit hergeholt, denn wüsste man über die Zusammenhänge bescheid, wäre es sicher theoretisch berechenbar nur nicht praktisch - wenn man dann alle Teilchen des Universum simulieren will reicht dein RAM wohl nicht ganz aus. :D

Berechenbarkeit kannst du beweisen indem du einfach einen Algorithmus angibst, also ein C-Programm oder eine Turingmaschine etc.


Ja, Church ist mir -informell- bekannt. Bezieht sich ja auch auf äquivalente Methoden wie die rekursiven Funktion oder das Lambda-Kalkül. Die müssten doch gleich mächtig sein. D.H. es gibt keine mächtigeren (abstrakten) Maschinen?
Mir ist vieles klar. Dennoch habe ich weiterhin meine Probleme, wenn es darum geht, Berechenbarkeit und Entscheidbarkeit klar voneinander zu differenzieren.
Nehmen wir mal ein Laborbeispiel:
Ich Frage ob A entscheidbar ist und ob A berechenbar ist. Wobei A eine unbestimmte Zeichenfolge ist.
Was muss denn nun gegeben sein, um A auf Berechenbarkeit und Entscheidbarkeit zu überprüfen?