De uma maneira geral, na máquina de Turing, um programa é uma função que, dependendo do estado corrente da máquina e do símbolo lido, determina o símbolo a ser gravado, o sentido do movimento da cabeça de gravação e o novo estado da máquina.