3-Band Turing Maschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:55 Fr 25.04.2008 | | Autor: | Docy |
Hallo alle zusammen,
wie kann man begründen, dass eine 3-Band Turing Maschine dieselbe Menge an turingberechenbaren Funktion liefert wie die 1-Band Turing Maschine?
Gruß Docy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:16 Fr 25.04.2008 | | Autor: | Gilga |
Du musst zeigen, dass man eine 3 Band TM auf einer 1-Band TM simulieren kann. TIPP: verwende als neues Alphabet 6Tupel des alten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:44 Di 29.04.2008 | | Autor: | Bastiane |
Hallo Gilga!
> Du musst zeigen, dass man eine 3 Band TM auf einer 1-Band
> TM simulieren kann. TIPP: verwende als neues Alphabet
> 6Tupel des alten.
Wenn man es so macht, zeigt man doch aber, dass eine 1-Band TM das Gleiche wie eine 3 Band TM leistet, oder nicht? Aber das ist auch das Einzige was Sinn macht, denke ich, deswegen war wohl die Aufgabenstellung schon falsch.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:46 Mi 30.04.2008 | | Autor: | Gilga |
Gerade darum gehts doch inder Aufgabenstellung -> zeigen dass beides gleich ist!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:12 Mi 30.04.2008 | | Autor: | Bastiane |
Hallo Gilga!
> Gerade darum gehts doch inder Aufgabenstellung -> zeigen
> dass beides gleich ist!
Naja, aber die eine Richtung, so wie ich die Aufgabenstellung verstehe, ist ja trivial. Ich meine, eine 3TM kann ja mindestens so viel wie eine 1TM, da kann man bei der 3TM ja einfach zwei Bänder leer lassen.
Viele Grüße
Bastiane
|
|
|
|
