Mapa mental
Máquina de Turing

Contenido del mapa
Máquina de Turing
Funcionamento
- Inicialmente o dado de entrada é escrito na fita. A cada transição a máquina de Turing pode ler um símbolo do alfabeto da fita, pode escrever sobre o mesmo, andar na fita para a direita ou para a esquerda e mudar de estado.
- Vamos supor que a fita possui uma primeira posição e que cada posição da fita sempre possui uma posição à sua direita, isto é, a fita é infinita para a direita.
- Cada posição da fita armazena um símbolo do alfabeto da fita. No início da execução da máquina, para uma entrada de tamanho n, as n primeiras posições da fita contém um símbolo da entrada. As demais posições da fita estão em branco (possuem o símbolo branco).
A máquina de Turing foi definida (TURING, 1937) por Alan Mathison Turing. Podemos entender uma máquina de Turing como um autômato finito com uma estrutura de dados auxiliar, neste caso uma fita.
Exemplo
- A imagem ilustra uma máquina de Turing que reconhece a linguagem L = { ω |ω tem a quantidade ímpar de a's}.
- Neste caso particular, a máquina de Turing anda sempre para a direita (representado pelo símbolo '->'), portanto, a máquina não recebe nenhuma informação da fita a menos da cadeia de entrada, sendo assim, a máquina de Turing tem o mesmo poder de computação que um autômato finito, o que era de se esperar, pois a linguagem reconhecida é uma linguagem regular.
Imágenes y archivos del mapa
Información
- Descripción
- Mapa Mental sobre Máquina de Turing, creado por Kykaze . el 13/11/2019.
- Creado por
- Kykaze .
- Visitas
- 0
- Valoración