Diskussion:Turingmaschine
- in beide Richtungen unsichtbares Band
Müsste es nicht heissen:
- in mindestens eine Richtung unendliches Band
Normalerweise startet eine Turingmaschine an der linken festen Seite eines unendlich langen Bandes, ja. --avatar
---
Es macht übrigens keinen Unterschied, ob eine Turing-Maschine eine oder mehrere Bänder verwendet. Ist das sicher? Ich habe gehört, es gebe Funktionen, die könnten mit zwei Bändern, aber nicht mit einem berechnet werden... -- Fgb
Aus dem hohlen Bauch heraus sage ich jetzt mal, dass es solche Funktionen nicht geben kann. Die Bänder sind abzählbar unendlich, d.h. es gibt eine Bijektion zwischen ihnen, und die muss die Turing-Maschine ausführen können. D.h. also, die T.M. kann mit einem Band zwei Bänder "emulieren". Der Rechenaufwand mag dabei steigen, aber letztendlich bleibt er von gleicher Ordnung, lediglich die Konstante ändert sich. -- Flups
Es gibt beliebige Speicher (im allgemeinen ein beliebiger Graph), also nicht nur Bänder. Die können alle die gleichen Funktionen berechnen, aber mit unterschiedlicher Effizienz. --Vulture
Wie schreibt man denn Turingmaschine jetzt? Turing-Maschine oder Turingmaschine? Google spuckt ca. 12200 Ergebnisse für "Turing-Maschine" und ca. 12300 für "Turingmaschine" aus, ist also auch nicht sehr aussagekräftig ... :)
Ich hab auf jeden Fall die Schreibweise im Artikel dem Titel angepasst ... --brunft 10:54, 12. Mär 2004 (CET)
--
Nach den neuen Regeln der Rechtschreibreform sind beide Schreibweisen möglich.
Siehe http://www.ids-mannheim.de/reform/c3.html
Hutschi
Eine Maschine mit zwei nichtgetakteten Bändern, könnte die mächtiger sein, als eine Turingmaschine? Hier spielte ja dann der Zufall eine Rolle. (Ich nenne sie nicht "Turingmaschine", denn es ist ja keine.)
Wenn eine Fliege da wäre, die sich auf das Band setzt und dafür sorgt, dass ein Zeichen nicht erkennbar wird, wäre die Maschine mächtiger, als die entsprechende Turingmaschine?
(Es wäre eine Turingmaschine, die irren kann.)
-- Hutschi 13:42, 16. Mär 2004 (CET)