Definição – O que significa Máquina de Turing?
Uma máquina de Turing é uma máquina teórica que manipula símbolos em uma fita, com base em uma tabela de regras. Embora a máquina de Turing seja simples, ela pode ser adaptada para replicar a lógica associada a qualquer algoritmo de computador. Também é particularmente útil para descrever as funções da CPU em um computador.
Alan Turing inventou a máquina de Turing em 1936 e se referiu a ela como uma “máquina” ou máquina automática.
Definirtec explica a máquina de Turing
A máquina de Turing não se destina a ser uma tecnologia de computação funcional; em vez disso, pretende ser uma máquina hipotética que representa uma máquina de computação. A máquina de Turing pode ajudar os cientistas da computação a compreender os limites da computação mecânica.
As máquinas de Turing modelam matematicamente um dispositivo que funciona mecanicamente usando uma fita. Esta fita contém símbolos, que a máquina pode escrever e ler, um após o outro, com a ajuda de uma cabeça de fita.
Mais especificamente, uma máquina de Turing inclui o seguinte:
- Fita: uma fita que se divide em células, uma ao lado da outra. Cada célula inclui um símbolo de um certo alfabeto finito. O alfabeto inclui um símbolo em branco exclusivo, bem como um ou mais outros símbolos. O volume de fita necessário para o cálculo está sempre incluído na máquina de Turing.
- Cabeça: uma cabeça capaz de escrever e ler símbolos na fita. Em alguns modelos, o cabeçote se move enquanto a fita é fixada.
- Registro de estado: um registro de estado para armazenar o estado da máquina de Turing. Há um estado inicial especial por meio do qual o registro de estado é inicializado.
- Tabela finita: uma tabela finita (às vezes referida como uma função de transição ou uma tabela de ação) de instruções, que geralmente são quíntuplas, mas ocasionalmente quádruplas.