A Análise de Computabilidade e Complexidade de Algoritmos

Faculdade Pitágoras  

São Luís, 19 de Maio de 2020

Aluno: Matheus dos Santos Sousa

Disciplina: Análise de Computabilidade e Complexidade de Algoritmos

                                         Atividade

              Como sabemos a maquina de Turing é parte fundamental na computação, sendo um modelo de máquina onde já se previa o que viria logo após e equivalentemente o calculo lambda de Church.

Essa equivalência em poder de expressão de dois formalismos definidos de maneiras radicalmente diferentes levou à proposição de que a classe de funções computadas pelos mesmos corresponde à classe das funções efetivamente calculáveis: qualquer outro formalismo para descrever procedimentos efetivamente calculáveis seria equivalente aos modelos já propostos. Todavia, uma vez que a noção de “efetivamente calculável” não é uma definição formal, e sim apenas uma noção intuitiva, tal proposição não é um teorema, mas sim apenas uma conjectura. Essa conjectura é denominada Tese de Church-Turing, Hoje em dia, a Tese de Church-Turing é amplamente aceita como uma definição adequada de o que é efetivamente calculável.

Tanto Church quanto Turing demonstraram que, em seus respectivos modelos de computação, o Entscheidungsproblem é indecidível: não existe uma máquina de Turing ou uma função no cálculo lambda capaz de determinar se uma proposição arbitraria em lógica de primeira ordem é verdadeira. Diversos outros problemas foram demonstrados indecidíveis nesses modelos de computação. Um exemplo clássico é o problema da parada, que consiste em determinar se a execução de uma dada máquina de Turing termina em um número finito de passos para uma dada entrada ou, analogamente, se uma dada fórmula em cálculo lambda possui uma forma normal. A importância de Tese de Church-Turing reside no fato de que, se a máquina de Turing representa adequadamente o que é efetivamente calculável, os limites de o que a máquina de Turing é capaz de fazer representam limites teóricos de computabilidade dos quais, em tese, não poderíamos escapar. Um estudo dos limites da computação é útil para que evitemos tentar solucionar problemas para os quais se sabe que uma solução é impossível.

Embora a máquina de Turing e o cálculo lambda tenham sido formulados há mais de setenta anos, esses formalismos permanecem relevantes como modelos de computabilidade ainda hoje.