0

Church-Turing

Mateus Silva
Mateus Silva

Essa artigo trata do Limite da Computação, aa tese que consegue saber se é possível ou não resolver um problema usando um computador.



"Computável"


Primeiro é preciso entender o que é algo "computável". Basicamente é quando existe um número finito de instruções que geram a resposta em um número finito de passos. Podemos pensar como: existe um algoritmo que execute uma quantidade finita de passos e gere o resultado esperado.


História


Na década de 1930 muitas pessoas procuraram definir formalismos para tentar provar se algo é ou não é computável. Nesse período Church e Turing tiveram grande destaque.


Church criou o Cálculo Lambda, mesmo cálculo que vemos em tantas linguagens de programação, em especial no paradigma funcional.


Scheme – Wikipédia, a enciclopédia livre


Já Turing definiu a Máquina de Turing, que é um tipo de computador digital hipotético que se baseia em ações executados sobre uma fita. Uma abstração seria pensar na fita como a memória do computador e que a cada etapa é feita a leitura em um espaço dessa fita e de acordo com o valor escolhe-se escrever na fita ou se deslocar na fita.


Representação de uma máquina de Turing acelerada. No início da... |  Download Scientific Diagram


Equivalência


Já se foi comprovado que os dois formalismos são equivalentes e conseguem demostrar quando algo é "efetivamente calculável".


Pedro Abreu :: Máquina de Turing, Decidibilidade e o Problema da Parada


Usasse se o termo "efetivamente calculável" porque é uma noção intuitiva, por tanto não é um teorema, mas uma tese conhecida como Tese de Church-Turing. Essa tese é amplamente aceita para definir o que é efetivamente calculável.


Exemplo famoso


Um problema famoso é o Problema da Parada. O problema pode ser definido como: é possível determinar se uma proposição arbitrária em lógica de primeira ordem é verdadeira?


Esse problema foi comprovado ser impossível de ser solucionar computacionalmente.


Uma boa analogia seria: você não consegue projetar um programa A que receba um outro programa B como entrada e determinar se o programa B encerra. Por exemplo, o programa A não iria conseguir se o programa B entra ou não em um loop infinito.


Limite da Computação


Essa tese consegue definir um limite para o que pode ser resolvido computacionalmente e tem um grande impacto sobre os programas de computador, pois com ele é possível comprovar que nem todo problema é efetivamente computável, ou seja, pode ser solucionado por um computador.


Fontes:

  1. https://homepages.dcc.ufmg.br/~nvieira/cursos/tl/a17s2/church-turing.pdf
  2. https://revistas.rcaap.pt/boletimspm/article/download/3870/2910
  3. https://www.infopedia.pt/$maquina-de-turing
0
8

Comentários (2)

0
Mateus Silva

Mateus Silva

16/07/2021 23:04

Muito obrigado, Thiago!

0
Thiago Silva

Thiago Silva

16/07/2021 22:46

Muito interessante o seu artigo, parabéns.

None

Brasil