Definição formal

Máquina de Turing com uma fita
Mais formalmente, uma máquina de Turing (com uma fita) é usualmente definida como uma 7-upla M = (Q,Σ,Γ,s,b,F,δ), onde

Q é um conjunto finito de estados
Σ é um alfabeto finito de símbolos
Γ é o alfabeto da fita (conjunto finito de símbolos)
é o estado inicial
é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação)
é o conjunto dos estados finais
é uma função parcial chamada função de transição, onde E é o movimento para a esquerda e D é o movimento para a direita.
Definições na literatura às vezes diferem um pouco, para tornar argumentos ou provas mais fáceis ou mais claras, mas isto é sempre feito de maneira que a máquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto {E,D} para {E,D,P}, onde P permite ao cabeçote permanecer na mesma célula da fita em vez de mover-se para a esquerda ou direita, não aumenta o poder computacional da máquina (Fonte - Michael Sipser - Int Teoria da Computação).