Maquina de turing

Maquina de Turing

No artigo “ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE
ENTSCHEIDUNGSPROBLEM”

Turing

descreveu

por

meios

de

demonstrações

matemáticas, o funcionamento de uma maquina que, na teoria, é capaz de realizar o calculo automático de qualquer função de acordo com instruções e estados apropriados, a esta maquina foi dado o nome de automatic machine (também denominada no artigo com
“a‐machine”). É importante resaltar que Turing não realizou a implementação física da
“a‐machine” e sim o desenvolvimento teórico da mesma. Além de desenvolver uma maquina que se realizam cálculos de funções automaticamente, Turing também objetivava criar um método para decidir se um problema é computável ou não, a sua maior motivação era solucionar o Entscheidungsproblem (problema de decisão) proposto por David Hilbert
(por causa disto que o titulo do artigo “ON COMPUTABLE NUMBERS, WITH AN
APPLICATION TO THE ENTSCHEIDUNGSPROBLEM”).
Através dos métodos matemáticos Turing provou que para qualquer algoritmo bem definido pode se desenvolver uma “a‐machine” que é capaz de simular uma máquina que execute tais procedimentos. Na realidade este era um dos objetivos de Turing, formalizar um sistema com a habilidade de simular qualquer outro sistema formal.
Porém, com a criação da “a‐machine” Turing também conseguir chegar ao seu outro objetivo, através da “a‐machine” foi demonstrada a existência de afirmações da matemática que são indecidíveis em conclusão a ideia de David Hilbert que tinha elaborado o Entscheidungsproblem, ou seja, não existe um procedimento efetivo para decidir se elas podem ser provadas dentro de um sistema matemático formal.
Para a computação atual este artigo tem imensurável valor, uma vez que, todos os computadores eletrônicos atuais são baseados no principio de funcionamento da maquina teórica de Turing. Exemplificando, a “a‐machine” move-se ou move símbolos, de uma posição para outra em uma fita, assim, podemos