Unterabschnitte
Eine NTM

entscheidet eine Sprache

falls gilt:
1.

und
2. Der Berechnungsbaum für jedes mögliche Eingabewort

ist endlich, d.h. jedes Wort wird nach endlicher Zeit entweder akzeptiert oder verworfen.
Aus jeder NTM kann man eine DTM machen. Man geht dabei den Berechnungsbaum mit einer Breitensuche durch
19.
Fußnoten
- ... durch19
- Hier darf man keine Tiefensuche verwenden. Das kann unter Umständen ins Auge gehen, da ein Berechnungsbaum ins Unendliche ragt, während ein anderer schon lange akzeptiert hat, man aber im unendlichen Berechnungsbaum immer tiefer geht und nie zum Ende kommt.