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