Há algum tempo, quando me formei em Ciência da Computação, fez parte do meu currículo uma matéria denominada Teoria da Computação. Naquela época, conseguir créditos suficientes para terminar essa matéria, foi realmente difícil. Enfim, consegui os créditos necessário, não me destaquei na matéria, fiquei na média aceitável para ser admitido para a próxima etapa (tenho muitas desculpas para isso: trabalho, transporte e várias outras no mesmo seguimento, quem não tem desculpas para uma média ruim?)

O fato é que um tempo após eu ter terminado o curso de Ciência da Computação, retomei o estudo dessa matéria (que diga-se de passagem: é fascinante), por conta de uma promessa que fiz de “retomar os estudos a matérias importantes assim que estivesse maduro o suficiente para entender e estudar o necessário para compreender o assunto”, coisa de adolescente.

Retomados os estudos, a primeira fonte que procurei foi o livro texto utilizado no passado para essa matéria. Eis que me deparo com Introdução a Teoria da Computação de Michael Sipser.

Após a leitura da introdução, logo percebi como o assunto é interessante e fascinante ao mesmo tempo. Após a euforia de entender a proposta do assunto (sim, eu fico realmente animado quando aprendo ou compreendo assuntos relacionados aos meus hobbies, você não fica?), decidi escrever um resumo sobre o que é Introdução a Teoria da Computação.

Os três temas centrais

Sipser, em seu livro, afirma que a Teoria da Computação é centrada em três grandes temas: Complexidade, Computabilidade e Autômatos, e os três temas são utilizados para responder um pergunta simples, de se entender, porém, difícil de responder:

Quais são as capacidades e limitações fundamentais dos computadores?

De acordo com Sipser, esta é uma pergunta que vem “tirando o sono” de muitos matemáticos, dês da época de Kurt Gödel, Alan Turing e Alonso Church até hoje. E é daí, desse tipo de problema, que surgiu a Teoria da Computação.

Complexidade

A complexidade, de acordo com Sipser em seu livro, tenta, na maioria das vezes, classificar o problema entre problemas fáceis e difíceis. É o mesmo que perguntar a alguém se “saber quem ganhou no par ou ímpar é fácil ou difícil”. Para saber se um problema é fácil ou difícil os computadores deveriam saber responder:

O que faz alguns problemas computacionalmente difíceis e outros fáceis?

Porém, essa é uma das perguntas da humanidade, que ainda não temos resposta. Assim, enquanto não encontramos essa resposta, foi criada uma tabela para classificar o problemas por nível de dificuldade computacional.

Esse é um tema discutido avidamente no campo da criptografia que está sempre em busca de códigos cada vez mais difíceis de se decifrar sem uma chave secreta ou senha, ou pelo menos, difícil o bastante para se decifrar nessa vida.

Computabilidade

Enquanto os matemáticos teóricos (citados a cima), estavam tentando encontrar uma forma de responder:

Dado um enunciado matemático, esse é verdadeiro ou falso?

Em outras palavra: dada uma conta (um enunciado matemático) é possível calculá-la/resolvê-la?

Esse é o grande desafio da área da computabilidade em teoria da computação.

Durante as várias tentativas para encontrar uma resposta para esse tipo de problema (o problema da Computabilidade), foram desenvolvidas várias teorias que levaram a teoria da construção dos computadores que utilizamos hoje (estamos falando de Alan Turing, lembra?).

Autômatos

Até o momento estamos apenas falando de matemática e quase nada de computação (mas computação é matemática, computação vem de computar, certo?). Embora matemática e computação sejam a mesma coisa, essas coisas se expressão de formas diferentes, então, como levar as teorias da Complexidade e Computabilidade, termos do campo matemáticos, para o campo da computação?

A resposta utilizada para tal pergunta remete aos autômatos.

Os autômatos são utilizados para expressar modelos computacionais. Sendo assim, sempre que necessário testar e comprovar alguma teoria matemática no campo da computação é possível criar essa ponte, com os autômatos fazendo o papel de máquinas teóricas computáveis.

Conclusão

Assim como em outras áreas das ciências, o ser humano tenta encontrar os limites do que está lindando. Nessa caso, a Teoria da Computação tenta encontrar “a capacidade e limitações fundamentais dos computadores”, utilizando, pelo menos, três recursos:

  1. Complexidade: classificar se o problema é fácil ou difícil de se resolver;
  2. Computabilidade: classificar se o problema admite solução matemática;
  3. Autômatos: criar uma solução ou algoritmo para resolução do problema no ambiente da computação.

Esse é o grande desafio e o fascínio dessa área. Simples e brilhante.

Referências