Máquina de Turing

Pesquisa sobre Alan Turing, sua máquina de estados e um exemplo do seu funcionamento. Luciano Pohlmann, Marcelo Souza e Vinicios Pontes.
Introdução a Computação - Sistemas de Informação.

1. Alan Turing e sua invenção
As Máquinas de Turing (MT) permaneceram no centro do desenvolvimento dos computadores/computação durante os últimos 70 anos. Alan Turing (1912-1954), conhecido como o fundador das Ciências da Computação, foi um brilhante matemático britânico, fazendo parte de uma geração entusiasmada quanto ao desenvolvimento da lógica e da matemática que futuramente resultaria no computador moderno.
Alan Turing procurou formalizar a ideia de algoritmo com as operações fundamentais e primitivas, as quais serviriam de base ao cálculo matemático. Sendo assim, a MT foi idealizada para ser um modelo de computação capaz de computar qualquer coisa que um humano possa computar. Até hoje, ainda não foi inventado um computador capaz de resolver um problema que a MT não possa resolver.
Turing foi condenado ao reconhecer sua homossexualidade, afastado do trabalho e submetido a castração química. Em 1954, teorias indicam que mordeu uma maçã envenenada com cianeto no seu laboratório, sendo classificado como suicídio, A campanha para o seu perdão começou em 2009, sendo declarada em público e assinada,

2. A máquina de Turing
A máquina de Turing possui um setor de controle e um dispositivo especial que funciona simultaneamente como entrada (referente a leitura - read), armazenamento, e saída (referente a escrita - write). Esse dispositivo é uma fita unidimensional que contém um número ilimitado de cédulas, na qual cada uma pode conter um único símbolo. Esta fita prolonga-se indefinidamente em ambos os sentidos e por isso pode conter uma quantidade infinita de informação. Esta informação pode ser lida e alterada em qualquer ordem, sendo uma característica importante da MT.
Associada à fita está uma cabeça de leitura-escrita que pode mover-se sobre a fita