Fundamentos de Computação

Máquina de Turing Em 1936, Alan Turing construiu um autómato imaginário, a Máquina de Turing. No seu estudo "Computing machinery and intelligence" (1950), Turing aborda a questão da inteligência da máquina, avaliando os argumentos face à possibilidade de criar uma máquina computacional inteligente e sugere respostas para estes argumentos, propondo o Teste de Turing como um teste empírico da inteligência.

A máquina de Turing pode ser vista como um sofisticado leitor de fitas, com uma fita arbitrariamente extensível. A fita é marcada nas secções, cada secção contêm um " 1 ", um " 0 " ou ser branca. Existe uma cabeça que verifica uma secção de cada vez.

A cabeça é capaz de efectuar apenas três acções:

Escrever na fita (ou apagar da fita), mas apenas na secção que está a ser verificada.

Alterar o estado interno.

Mover a fita 0 ou 1 espaços, para o esquerda ou direita.

As suas características e comportamento qualificam a Máquina de Turing como uma máquina de estado finito (MEF), ou um autómato finito. Em qualquer momento, a máquina está num estado descritivel. e, entre este momento e a próxima etapa discreta, a máquina lê a sua entrada da fita, consulta as regras que controlam o seu comportamento, e considerando o input e o estado actual, determina qual o comportamento que deve efectuar (isto é apagar, escrever ou mover a fita) e que estado interno deve ser assumido.

A Máquina de Turing pode ser descrita como uma mapa, descrevendo um conjunto de acções para cada estado, ou um diagrama de transição de estado, representando a mesma informação na forma de diagrama.

A potência da Máquina de Turing reside na potencialidade de armazenando da sua fita. A sua extensão infinita significa que o dispositivo pode recorrer a um espaço de armazenamento externo ilimitado como " o papel " para o seus cálculos, produzindo também um output de tamanho ilimitado. Assim, a fita guarda o input para a máquina, age como armazenamento