Mind map
Máquina de Turing

Map content
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.
Images and files in the map
Information
- Description
- Mind Map on Máquina de Turing, created by Kykaze . on 13/11/2019.
- Created by
- Kykaze .
- Views
- 0
- Rating