„Turing-gép” változatai közötti eltérés

Az előbbi kiszámolt eredményre a következőképp lehet jutni: adott véges n elemű ábécé feletti 1<k-állapotú Turing-gép egyértelműen megadható egy átmenetfüggvénnyel. Ez olyan táblázat, melynek n oszlopa és k sora van, tehát n×k cellája. Minden cellában az átmenetfüggvény egy lehetséges értéke áll, egy elemhármas, mely egy külső, egy belső és egy címszimbólumból álló rendezett elemhármas, ilyen pedig n×k×3 db. van. Mármost bármely cellába elvileg bármely lehetséges elemhármas beírható (persze az így kapott átmenetfüggvények többsége olyan gépet eredményez, ami semmi értelmeset nem csinál, például ha minden kimenő állapot stop-állapot, de bizony ez is egy Turing-gép), tehát n×k×3 elem n×k-adosztályú [[variáció (matematika)|variáció]]járól van szó. Ezek száma pedig (n×k×3)^n×k. A becslés javítható, ha a stop-állapotot nem számítjuk külön sornak (mert ha a gép stop-állapotba kerül, akkor már nem számít ki több átmenetfüggvény-értéket, az stopnak megfelelő táblázatsor üres), az így kapott eredmény n×k×3^n×(k-1). Azért is érdemes ezt részletesen taglalni, mert észre lehet venni mindebből, hogy az adott ábécé feletti izomorf Turing-gépek (ti. ezek osztályai) felsorolhatóak, vagyis adott ábécé felett megszámlálhatóan végtelen sok nem-izomorf (Turing-) algoritmus létezik!