Turingmaschine Funktion |
| 11.07.2009, 20:48 | Krikus | Auf diesen Beitrag antworten » |
| Turingmaschine Funktion folgende 1 bandige Turingmaschine M mit Startzustand q0 und Endzustand qe ist gegeben: Welche zweistellige Funktion fM(x1,x2) und dreistellige Funktion fM(x1,x2,x3) über die natürlichen Zahlen berechent diese Maschine? Ich weiß was die Turingmaschien macht, Egal ob eine 0 oder 1 auf dem Band steht, er bleibt im Zustand q0. Sobald ein B auftaucht ist er im Enzustand und schreibt ein B auf das Band. Somit würde er egal was man eingibt nie ein Ergebniss bekommen. Aber was muss ich nun bei den Funktionen angeben? Gruß Krikus |
||
| 11.07.2009, 22:24 | tigerbine | Auf diesen Beitrag antworten » |
| RE: Turingmaschine Funktion Vielleicht wäre auch das eine gute Adresse? http://www.informatikerboard.de/index_start.php |
||
| 12.07.2009, 00:17 | Bjoern1982 | Auf diesen Beitrag antworten » |
Ein Board für Informatik würde ich auch vorschlagen aber nicht dieses, so wenig wie da gepostet oder geantwortet wird 
Mit etwas Suchen findet man aber bestimmt ein paar Alternativen 
|
||
| 12.07.2009, 11:46 | tigerbine | Auf diesen Beitrag antworten » |
Bjoern, ein solcher Seitenhieb von dir? 
|
||
| 12.07.2009, 11:55 | Bjoern1982 | Auf diesen Beitrag antworten » |
|
||
| 12.07.2009, 12:00 | kiste | Auf diesen Beitrag antworten » |
Oder wir lösen das Problem einfach intern. Hab mal kurz in meinem schlauen Buch Turingberechenbar nachgeschlagen. Ich vermute du mal du arbeitest auf den natürlichen Zahlen, die Eingabe wird kodiert auf das Band geschrieben in der Form bin(x1)Bbin(x2)Bbin(x3)B etc. Dann löscht die Turingmaschine ja alles bis zum ersten B Im Fall f(x1,x2) bleibt also B...Bq_ebin(x2)B...B auf dem Band stehen. Was berechnet die Funktion also? Was bleibt im Fall f(x1,x2,x3) stehen? Was bedeutet das? |
||
| Anzeige | ||
|
|
||
| 12.07.2009, 12:08 | Krikus | Auf diesen Beitrag antworten » |
Wenn man es so betrachet, dann würde bei f(x1,x2) als Ergebnis auf dem Band nur x2 stehen bleiben. Bei f(x1,x2,x3) nur x2 und x3 getrennt durch ein B auf dem Band stehen bleiben. |
||
| 12.07.2009, 12:14 | kiste | Auf diesen Beitrag antworten » |
Ja, und jetzt kommt es entscheidend auf die Definition von berechenbar an die ihr hattet. Laut meiner Definition ist f(x1,x2) = x2 und f(x1,x2,x3) undefiniert. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
