Exemplo

A máquina de Turing a seguir tem um alfabeto {'0', '1'}, onde 0 representa o símbolo branco. Ela espera uma série de 1's na fita, com o cabeçote inicialmente no 1 mais à esquerda, e duplica os 1's com um 0 no meio. Por exemplo, "111" torna-se "1110111". O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1. A tabela de ação é dada a seguir.

Old Read Wr. New Old Read Wr. New
St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St.
- - - - - - - - - - - - - - - - - - - - - - - -
s1 1 -> 0 D s2 s4 1 -> 1 E s4
s2 1 -> 1 D s2 s4 0 -> 0 E s5
s2 0 -> 0 D s3 s5 1 -> 1 E s5
s3 0 -> 1 E s4 s5 0 -> 1 D s1
s3 1 -> 1 D s3
A primeira linha desta tabela pode ser lida como: "Se a máquina estiver no estado s1 e o símbolo lido pelo cabeçote for 1, então escreva o símbolo 0, mova uma posição para a direita e mude o estado para s2".

Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito)

Passo Estado Fita Passo Estado Fita
- - - - - - - - - - - - - - - - -
1 s1 11 9 s2 1001
2 s2 01 10 s3 1001
3 s2 010 11 s3 10010
4 s3 0100 12 s4 10011
5 s4 0101 13 s4 10011
6 s5 0101 14 s5 10011
7 s5 0101 15 s1 11011
8 s1 1101 -- pára --
O comportamento desta máquina pode ser descrito como um laço (loop): ele inicia em s1, substitui o primeiro 1 com um 0, então usa o s2 para mover para a direita, passando pelos 1's e pelo primeiro 0 encontrado. S3 então passa pela próxima seqüência de 1's (inicialmente há nenhuma) e substitui o primeiro 0 que encontra por um 1. S4 move de volta para a esquerda, passando pelos 1's até encontrar um 0 e vai para o estado s5. S5 então move para a esquerda, passando pelos 1's até achar o 0 que foi originalmente escrito por S1. Ele substitui o 0 por 1, move uma posição para a direita e entra no estado s1 novamente para outra execução do laço. Isso continua até s1 achar um 0 (este é o 0 que fica entre as duas cadeias de 1's), situação na qual a máquina pára.