Inteligência Artificial - Máquina de Turing

Inteligência Artificial
Jessica Rutiely
Samuel Praxedes

Thaiza Medeiros
Valesca Juliane

2

Máquina de Turing
É um dispositivo teórico conhecido como máquina universal, muitos anos antes de existirem os modernos computadores digitais. É um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital. Máquina de Turing com uma fita

3

Uma máquina de Turing (com uma fita) é usualmente definida como uma Tupla
, onde:



é um conjunto finito de estados



é um alfabeto finito de símbolos



é o alfabeto da fita (conjunto finito de símbolos) é o estado inicial




é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação) é o conjunto dos estados finais





onde

⇒ é uma função parcial chamada função de transição, é o movimento para a esquerda e é o movimento para a direita.

4

Máquina de Turing com k fitas
Uma máquina de Turing com k fitas também pode ser descrita como uma 7-upla
, onde:



é um conjunto finito de estados



é um alfabeto finito de símbolos



é o alfabeto da fita

(conjunto finito de símbolos)



é o número de fitas



é o estado inicial



é o símbolo branco



é o conjunto dos estados finais



⇒ é uma função parcial chamada função de transição, onde o movimento para a esquerda e é o movimento para a direita.

é

5

Máquinas de Turing determinísticas e não-determinísticas Se a tabela de ação tem no máximo uma entrada para cada combinação de símbolo e estado então a máquina é uma máquina de
Turing determinística (MTD). Se a tabela de ação contém múltiplas entradas para uma combinação de símbolo e estado então a máquina é uma máquina de Turing nãodeterminística (MTND ou MTN).

6

Teste de Turing
Em 1950, na revista filosófica Mind, Alan Turing publicou um artigo chamado “Computing Machine and