Turing machine, hypothetical computing device introduced in 1936 by the English mathematician and logician Alan M. Turing. Turing concebeu originalmente a máquina como uma ferramenta matemática que poderia reconhecer infalivelmente propostas indecidíveis – ou seja, aquelas afirmações matemáticas que, dentro de um dado sistema axiomático formal, não podem ser demonstradas como verdadeiras ou falsas. (O matemático Kurt Gödel tinha demonstrado que tais propostas indecidíveis existem em qualquer sistema suficientemente poderoso para conter a aritmética). Turing, em vez disso, provou que nunca poderá existir qualquer método algoritmico universal para determinar se uma proposta é indecidível.
A máquina Turing não é uma máquina no sentido vulgar, mas sim um modelo matemático idealizado que reduz a estrutura lógica de qualquer dispositivo informático ao seu essencial. Como previsto por Turing, a máquina desempenha as suas funções numa sequência de passos discretos e assume apenas um de uma lista finita de estados internos em qualquer momento. A própria máquina consiste de uma fita infinitamente extensível, uma cabeça de fita capaz de executar várias operações na fita, e um mecanismo de controlo modificável na cabeça que pode armazenar direcções a partir de um conjunto finito de instruções. A fita é dividida em quadrados, cada um dos quais ou está em branco ou tem impresso sobre ela um de um número finito de símbolos. A cabeça da fita tem a capacidade de mover-se para, ler, escrever e apagar qualquer quadrado e pode também mudar para outro estado interno a qualquer momento. Qualquer acto deste tipo é determinado pelo estado interno da máquina e pelo estado do quadrado digitalizado num dado momento. A saída da máquina – ou seja, a solução para uma consulta matemática – pode ser lida a partir do sistema uma vez que a máquina tenha parado. (Contudo, no caso das propostas indecidíveis de Gödel, a máquina nunca pararia, e isto ficou conhecido como o “problema de paragem”)
Ao incorporar todas as características essenciais do processamento de informação, a máquina Turing tornou-se a base para todos os computadores digitais subsequentes, que partilham o esquema básico da máquina de um dispositivo de entrada/saída (fita e leitor), memória (armazenamento do mecanismo de controlo), e unidade central de processamento (mecanismo de controlo).