- 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