Was heißt Turingvollständigkeit

[Henryk Plötz]

Moin,

Was soll sie da lesen, wenn anfangs nur Leerzeichen auf dem Band stehen?

Das Band ist am Anfang mit Daten beschrieben (die evtl. auch als Programm interpretiert werden).

"Kommt drauf an"[tm]. Es gibt in dieser Hinsicht keine Beschränkung. Wenn es um Berechenbarkeit geht, nimmt man zwar üblicherweise ein bestimmtes Format (Systemprogrammierer würden jetzt "calling convention" sagen), aber vorgeschrieben ist das nicht.

Ein beliebtes Problem sind zum Beispiel "Fleißige Biber" (engl. busy beaver), also Programme die auf einem leeren Band starten und möglichst viel draufschreiben.