Annak eldöntése, hogy egy determinisztikus véges automata egy adott inputot elfogad-e.

Annak eldöntése, hogy egy adott Turing-gép az üres inputtal elindítva megáll-e.

Annak eldöntése, hogy egy adott Turing-gép legfeljebb 10 lépést tesz-e az üres inputon.

Annak eldöntése egy Turing-gépről, hogy ötnél több állapota van-e.

Annak eldöntése, hogy egy adott Turing-gép egy adott inputot elfogad-e.