Computabilidade e complexidade são dois conceitos fundamentais para entender quais problemas podem ser resolvidos com a ajuda de computadores

 

Apesar do extraordinário avanço da computação, há mais problemas não computáveis (que não podem ser resolvidos por computadores) do que computáveis (que podem ser resolvidos por computadores), diz o professor Luciano Silva, que vai lecionar a disciplina Teoria da Computação e Linguagens Formais no novo curso de Ciência da Computação do Insper. Bacharel em Ciência da Computação, mestre em Matemática Aplicada e doutor em Ciência da Computação pela Universidade de São Paulo, Silva explica a seguir a importância de entender o que pode ou não ser resolvido por computadores e o grau de complexidade dos problemas que os cientistas da computação vão buscar resolver em diversas áreas.

 

Teoria da Computação é uma das disciplinas do novo curso de Ciência da Computação do Insper. Por que ela é importante?

Teoria da Computação e Linguagens Formais é uma das disciplinas fundamentais para uma formação sólida de um cientista da computação. Ela permite que problemas sejam tratados como problemas de linguagens e, a partir disso, trabalhar com conceitos como computabilidade e complexidade. Por exemplo, saber se um programa desenvolvido por um programador está correto ou não. Para isso, especificamos uma gramática para a linguagem de programação utilizada pelo programador, e o problema de decidir se o programa está correto ou não pode ser transformado no problema de decidir se o programa está de acordo com essa gramática ou não. Usamos então uma teoria criada pelo linguista americano Noam Chomsky, chamada Hierarquia de Linguagens de Chomsky. Essa transformação permite definir uma classe de problemas chamados Problemas de Decisão. Para resolvê-los, precisamos escrever reconhecedores, que são a base para implementar compiladores para linguagens de programação. Durante a disciplina, os alunos projetam uma linguagem de programação completa e implementam um compilador para ela.

Como e quando surgiu a Teoria da Computação?

Historicamente, a Teoria da Computação surgiu dos trabalhos de dois grandes matemáticos: o americano Alonzo Church e o britânico Alan Turing. Church desenvolveu um sistema lógico em 1930 chamado Cálculo Lambda (ou Lambda-Cálculo), que permitia realizar ações semelhantes ao que conhecemos como computação em sistemas lógicos. Church foi orientador de Turing, considerado o pai da Ciência da Computação. Seu trabalho seminal com Máquinas de Turing, de 1936, permitiu formalizar a noção do que é computável ou não: X é computável se, e somente se, existe uma Máquina de Turing capaz de computar X. Formalmente, podemos provar que o Cálculo Lambda e as Máquinas de Turing são equivalentes em termos de poder computacional. Tudo o que uma computa a outra também é capaz de computar. De forma mais prática, as Máquinas de Turing representam o que conhecemos por hardware, enquanto o Cálculo Lambda é o software.

O que o aluno vai aprender nessa disciplina?

Inicialmente, o aluno aprende a transformar problemas em linguagens formais. A partir disso, estuda a noção de computabilidade, ou seja, o que pode ser resolvido ou não por computadores. Existem duas classes de problemas: problemas não computáveis (que não podem ser resolvidos por computadores) e problemas computáveis (que podem ser resolvidos por computadores). Infelizmente, para os não computáveis, não há o que fazer. Para os computáveis, estudamos o seu nível de complexidade. Existem classes de complexidade denominadas P, NP, NP-Completo e NP-Difícil. Os problemas da classe P (tempo polinomial determinístico) são aqueles que podem ser resolvidos de forma eficiente. Os da classe NP (tempo polinomial não determinístico) são aqueles para os quais não se conhece uma solução eficiente, mas, se você apresentar uma proposta de solução, ela pode ser verificada eficientemente. Dizer que não se conhece uma solução não significa que ela não exista. Nessa linha de complexidade, existe um prêmio internacional de cerca de US$ 1 milhão para quem conseguir provar que P = NP, ou seja, que todo problema cuja solução possa ser verificada eficientemente também possui uma solução geral eficiente. Toda essa discussão é fundamental para que um profissional de ciência da computação, ao analisar um novo problema, saiba decidir se ele é computável ou não. Sendo computável, é preciso avaliar se ele pode ser resolvido de forma eficiente ou, caso o problema se prove como NP, NP-Completo ou NP-Difícil, propor estratégias para atacar essa complexidade.

Existem muitos problemas que jamais poderão ser resolvidos por um computador?

Sim, há muitos problemas para os quais não existe solução computacional. O exemplo mais clássico é: existe um programa que consegue verificar se outro programa sempre termina a sua execução? Esse problema é conhecido como Problema da Parada e é não computável em qualquer modelo de computação. Esse nome, Problema da Parada, foi cunhado devido ao termo informal de um “problema parar sua execução”. Trata-se de um problema teórico muito importante e com profundas consequências práticas. Ao analisamos um problema e decidirmos propor uma solução computacional para ele, devemos nos perguntar se tal solução computacional existe ou não. Se o problema que estivermos tentando resolver puder ser transformado (ou reduzido, numa linguagem mais formal) ao Problema da Parada, podemos desistir do objetivo: não existirá nenhum modelo de computação que consiga suportar o desenvolvimento de programa para resolver esse problema. E é surpreendente que existam mais problemas não computáveis do que computáveis. Só conseguimos chegar a esse resultado usando ferramentas matemáticas mais poderosas e está relacionado com a chamada Aritmética Cardinal, que é uma aritmética que trabalha com números infinitos: o tamanho do conjunto dos problemas computáveis é um determinado infinito (chamado ℵ0), e o tamanho do conjunto dos problemas não computáveis é 2^ℵ0. Saber manipular essas definições formais é uma habilidade importante na sólida formação de um bacharel em Ciência da Computação.

Quais são os principais modelos de computação que os alunos vão estudar durante o curso?

Inicialmente, os alunos estudarão os modelos de Cálculo Lambda e Máquinas de Turing. Esses modelos são chamados de modelos de computação convencionais. Quando esses modelos não são suficientes para atacar de maneira efetiva um problema, podemos usar modelos de computação não convencionais. Nessa linha, os alunos estudarão os modelos aproximativos, os modelos baseados em oráculos, os modelos de difusão (como os autômatos celulares), os modelos moleculares (onde usamos DNA, RNA e proteínas para fazer computações) e os modelos quânticos.

Durante o curso, que atividades os alunos terão para aplicar na prática o que aprenderem na disciplina Teoria da Computação?

Os alunos colocarão essa teoria em prática construindo reconhecedores de linguagens (como compiladores e interpretadores), analisando a computabilidade e a complexidade de problemas, propondo estratégias para lidar com a complexidade de problemas e implementando programas para máquinas não convencionais como autômatos celulares, sistemas biológicos e computadores quânticos.