Computabilidade
Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. A computabilidade de um problema é intimamente ligada à existência de um algoritmo para resolver o problema.
Imagem: MarioJAl · BY-SA · Openverse
A ideia central da computabilidade é a dos problemas computacionais, que é uma tarefa cuja computabilidade pode ser explorada. Outros tipos de problemas incluem problemas de busca e problemas de otimização. Um dos objetivos da Teoria da Computabilidade é determinar que problemas, ou classes de problemas, podem ser resolvidos em cada modelo de computação.
Imagem: User:RobinK · BY-SA · Openverse
Um modelo da computação é uma descrição formal de um tipo particular de processo computacional. A descrição normalmente toma forma de uma máquina abstrata cujo objetivo é realizar uma dada tarefa. Modelos gerais da computação equivalentes à máquina de Turing incluem: Uma computação consiste de uma expressão lambda inicial (ou duas, se deseja-se separar a função e suas entradas) mais uma sequência finita de termos lambda, cada um deduzido de termo precedente por uma aplicação de redução Beta. É um conceito que possui muitas similaridades com cálculo lambda, mas existem diferenças importantes (ex.: combinador de ponto fixo Y tem uma forma normal em lógica combinatória, mas não em cálculo lambda). Lógica combinatória foi desenvolvida com grandes ambições: entender a natureza dos paradoxos, fazer as bases da matemática mais econômicas (conceitualmente) e eliminar a noção de variáveis (assim esclarecendo seus papeis na matemática).
Com os modelos computacionais em mãos, somos capazes de determinar quais são seus limites, ou seja, quais classes de linguagens eles aceitam?
Poder das máquinas de estados finita
Cientistas da Computação chamam quaisquer linguagens que podem ser aceitas por máquinas de finitos estados de linguagem regular. Por causa da restrição que o número de estados é finito, nestas máquinas, podemos perceber que para achar uma linguagem que não é regular temos que construir uma linguagem que requer uma infinidade de estados. Um exemplo desta é o conjunto de todas as Strings que possuem unicamente as letras 'a' e 'b' com mesmo número de letras para 'a' e para 'b'. Para perceber o por quê essa linguagem não pode ser corretamente reconhecida por uma máquina de finitos estados, assumimos primeiramente que tal máquina M existe. M tem de ter um número de estados n. Agora consideremos a String x consistindo de (n+1) 'a's seguidos por (n+1) b's.
Poder do autômato com pilha (pushdown)
Cientistas da Computação definem a linguagem que pode ser aceita por um automato pushdown como uma linguagem livre de contexto, que pode ser especificada como uma gramática livre de contexto. A linguagem que contém strings com números iguais de a's e b's, que foi mostrada que não é uma linguagem regular, pode ser decidida através de um automato com pilha. Além disso, em geral, um automato com pilha pode se comportar como uma máquina de finitos estados, então ela pode decidir qualquer linguagem regular. Este modelo de computação é, então, estritamente mais poderoso que a máquina de estados finita. Entretanto, há linguagens que não podem ser decididas nem por autômatos com pilha. O resultado é similar àquele das expressões regulares e não será detalhado aqui. Existe o Lema do Bombeamento para linguagens livres de contexto. Um exemplo dessa linguagem é o conjunto dos números primos.
Poder da máquina de Turing
Máquinas de Turing podem decidir quaisquer linguagens livre de contexto, em complemento às linguagens não decidíveis pelo autômato com pilha, como a linguagem formada por números primos. Por isso, é um modelo de computação estritamente mais poderoso. Porque a máquina de Turing tem a habilidade de "voltar" na "fita" de entrada, é possível para ela executar por um grande período de tempo, de modo que não é possível com os outros modelos computacionais descritos anteriormente. É possível construir uma máquina de Turing que jamais irá parar de executar (halt) em algumas entradas. Dizemos que a máquina de Turing pode decidir uma linguagem se esta eventualmente parar em todas as entradas e dar uma resposta. Uma linguagem que pode ser assim decidida é chamada de linguagem recursiva. Podemos também descrever uma máquina de Turing que irá eventualmente dar halt e dar uma resposta para quaisquer entradas em uma linguagem, mas que irá executar para sempre para strings de entrada que não estão na linguagem. Tais máquina de Turing podem nos dizer se uma dada string de entrada está na linguagem, mas nós nunca teremos certeza baseado no comportamento dela se uma string não pertence a linguagem, visto que a máquina pode executar para sempre em tais casos. Uma linguagem que é aceita pela máquina de Turing é chamada de linguagem recursivamente enumerável.
Problema da Parada
O problema da parada é um dos mais famosos problemas da ciência da computação, porque tem profundas implicações na teoria da computabilidade e como usamos computadores no dia-a-dia. O problema pode ser resumido em: Dadas a descrição de uma máquina de Turing e suas entradas iniciais, determine se o programa, quando executado com esta entrada, para. Alternativamente temos se ele executa para sempre sem parar. Aqui estamos perguntando não uma simples questão sobre um número primo ou um palíndromo, mas estamos interessados na capacidade de resposta de uma máquina de Turing sobre outra máquina de Turing. Pode ser mostrado (veja artigo principal: Problema da parada) que não é possível construir uma máquina de Turing que pode responder em todos os casos.
Além das linguagens recursivamente enumeráveis
O problema da parada é fácil de se resolver, entretanto, se nós permitirmos que a máquina de Turing que decide isto execute para sempre quando uma dada entrada que é a representação de uma máquina de Turing que não para. A linguagem da parada é, então, recursivamente enumerável. É possível construir uma linguagem que não é recursivamente enumerável, entretanto. Um simples exemplo desta linguagem é o complemento da linguagem da parada; isto é, a linguagem que contém todas as máquinas de Turing pareadas com entradas de strings onde as máquinas não param com suas respectivas entradas. Para perceber que essa linguagem não é recursivamente enumerável, imagine que nós construímos uma máquina de Turing M que é capaz de dar uma resposta definitiva para todas as máquinas de Turing, mas que pode executar para sempre em qualquer máquina de Turing que em algum momento no futuro pare. Podemos então construir outra máquina de Turing M' que simula a operação desta máquina, juntamente com simulando diretamente a execução da máquina dado as entradas também, através da intercalação da execução dos dois programas. Já que a simulação direta irá eventualmente parar se o programa que está simulando parar, e visto que, por hipótese, a simulação de M irá em algum momento adiante parar se a entrada do programa nunca parar, sabemos que M' irá eventualmente ter uma de suas versões paralelas paradas. M' é então um decisor para o problema da parada. Mostramos previamente, entretanto, que o problema da parada era indecidível. Temos uma contradição, e mostramos que nossa hipótese de que M existe é incorreta. O complemento da linguagem da parada é, então, não recursivamente enumerável.
Os primeiros resultados relevantes na direção da solução destas questões foram dados no ano de 1931 pelo matemático austríaco Kurt Gödel em seu artigo "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", onde ele define questões solúveis mecanicamente como aquelas onde a solução pode ser dada por uma função recursiva (em estudos prévios Gödel acreditava que as funções algoíitmicas fossem funções recursivas primitivas, mas felizmente descartou tal hipótese). Este artigo é famoso por ter mostrado que uma das questões do Programa de Hilbert era insolúvel. O próximo passo relevante é dado por Alan M. Turing, em seu artigo "On Computable Numbers, with an Application to the Entscheidungsproblem", onde ele diz que um problema é solúvel mecanicamente se existe uma Máquina de Turing que resolve aquele problema, e demonstra que existe pelo menos um problema insolúvel algoritmicamente (se tal problema, definido em toda sua generalidade, pode ser eficientemente resolvido por cérebros humanos ainda é uma polêmica questão em aberto). A demonstração de Turing, apesar de ter um apelo intuitivo bastante didático para os estudantes de computação, é basicamente a mesma do artigo de Gödel.
