Turing

Turing propôs um modelo abstrato de computação, conhecido como Máquina de Turing, com o objetivo de explorar os limites da capacidade de expressar soluções de problemas.

Trata-se, portanto, de uma proposta de definição formal da noção intuitiva de algoritmo.

Diversos outros trabalhos, como Máquina de Post (Post - 1936) e Funções Recursivas (Kleene - 1936), bem como a Máquina Norma e o Autômato com Pilhas, resultaram em conceitos equivalentes ao de Turing.

O fato de todos esses trabalhos independentes gerarem o mesmo resultado em termos de capacidade de expressar computabilidade é um forte reforço no que é conhecido como Hipótese de Church ou Hipótese de Turing-Church:

"A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação”

Afirma que qualquer função computável pode ser processada por uma Máquina de Turing, que existe um algoritmo expresso na forma de Máquina de Turing capaz de processar a função.

Como a noção intuitiva de algoritmo não é matematicamente precisa, é impossível formalizar uma demonstração de que a Máquina de Turing é, efetivamente, o mais genérico dispositivo de computação.

Supondo verdadeira a Hipótese de Church, pode-se afirmar que para:

a) Função Computável: É possível construir uma Máquina de Turing (ou formalismo equivalente) que compute a função;

b) Função Não-Computável: Não existe Máquina de Turing (ou formalismo equivalente) que compute a função.

Turing propôs um modelo abstrato de computação, conhecido como Máquina de Turing, com o objetivo de explorar os limites da capacidade de expressar soluções de problemas.

Trata-se, portanto, de uma proposta de definição formal da noção intuitiva de algoritmo.

Diversos outros trabalhos, como Máquina de Post (Post - 1936) e Funções Recursivas (Kleene - 1936), bem como a Máquina Norma e o Autômato com Pilhas, resultaram em conceitos equivalentes ao de Turing.

O fato de todos esses trabalhos independentes gerarem o mesmo resultado em termos de capacidade de expressar computabilidade é um forte reforço no que é conhecido como Hipótese de Church ou Hipótese de Turing-Church:

"A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação”

Afirma que qualquer função computável pode ser processada por uma Máquina de Turing, que existe um algoritmo expresso na forma de Máquina de Turing capaz de processar a função.

Como a noção intuitiva de algoritmo não é matematicamente precisa, é impossível formalizar uma demonstração de que a Máquina de Turing é, efetivamente, o mais genérico dispositivo de computação.

Supondo verdadeira a Hipótese de Church, pode-se afirmar que para:

a) Função Computável: É possível construir uma Máquina

...