Vyčíslitelnost a složitost výpočtů

Ukázka Turingova stroje počítajícího faktoriál

Vstup: 1. páska = n jedniček

Výstup: 2. páska, n! jedniček

Krokujte stroj a všímejte si, jakým způsobem funguje, sledujte dílčí procedury v průběhu výpočtu, jako např. násobení.

d(0, , )=(99, , ,1, )
d(0,1, )=(1, ,R,1, )
d(1, ,1)=(10, , ,1,R)
d(1,1,1)=(2,1, ,x,R)
d(2,1, )=(3,1, ,0,L)
d(2,1,?)=(2,1, ,?,R)
d(3,1,0)=(3,1, ,0,L)
d(3,1,1)=(4,1, ,1,L)
d(4,1,1)=(4,1, ,1,L)
d(4,1,x)=(1,1, ,x,R)
d(3,1,x)=(5,1, ,1,L)
d(5,1,x)=(5,1, ,1,L)
d(5,1, )=(1,0,R, ,R)
d(10, ,1)=(10, , ,1,R)
d(10, ,0)=(10, , ,1,R)
d(10, , )=(11, , , ,L)
d(11, ,1)=(11, , ,1,L)
d(11, , )=(12, ,L, ,R)
d(12, ,1)=(99, , ,1, )
d(12,0,1)=(13,1,L,1, )
d(13,0,1)=(13,1,L,1, )
d(13, ,1)=(13, ,R,1, )
d(13,1,1)=(1, ,R,1, )