Ein wichtiges Problem im Zusammenhang mit der TM ist die Frage, ob eine TM angesetzt auf eine beliebige Eingabe nach endlich vielen Schritten anhält. Das sog. "Halteproblem" wird folgendermassen formuliert:

Gibt es ein Entscheidungsverfahren, das für jeden Algorithmus und für jede mögliche Eingabe entscheidet, ob der Algorithmus angesetzt auf die Eingabe irgendwann anhält ?

Mittels eines Beweisverfahrens kann dabei gezeigt werden, dass dieses Halteproblem nicht gelöst werden kann (siehe dazu [Stu95], S.212). Es gibt keine TM (und somit keinen Algorithmus), die jede beliebige TM und jedes beliebige Eingabewort als Eingabe erhalten kann und entscheidet, ob die TM dabei anhält.