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.

Os modelos mais estudados da computabilidade são as funções Turing-Computáveis e as  funções μ-recursivas, e o cálculo lambda, todos os quais têm poderes computacionais equivalentes. Outras formas de computabilidade são também estudadas: noções de computabilidade mais fracas que as máquinas de Turing são estudadas na Teoria dos autômatos, enquanto que noções mais fortes que as máquinas de Turing são estudadas no campo da Hipercomputação.

A ideia central da computabilidade é a dos problemas computacionais, que é uma tarefa cuja computabilidade pode ser explorada.

Existem dois tipos de problemas:

• Os problemas de decisão fixam um conjunto S, que pode conter strings, números naturais, ou outros objetos retirados de um conjunto maior U. Uma instancia particular do problema é decidir, dado um elemento de u de U, se u está contido em S. O Teste de Primalidade é um desses exemplos.
• Os problemas de função consistem de uma função f de um conjunto U para um conjunto V. Uma instância do problema é computar, dado um elemento u de U, o elemento correspondente f(u) em V. Por exemplo, U e V podem ser o conjunto de todas as strings binárias, e f pode ser uma função que recebe uma string e retorna a string obtida ao reverter todos os dígitos da entrada (logo, f(0101) = 1010).

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.

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:

• Cálculo Lambda

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.

• Lógica Combinatória

É 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).

• Funções μ-recursivas

Uma computação consiste de uma funções μ-recursiva, i.e. a sequência que a define, quaisquer valores de entrada e uma sequência de funções recursivas aparecendo na sequência que a define com entradas e saídas. Portanto, se na sequência definida de uma função recursiva f(x) as funções g(x) e h(x,y) aparecem, então os termos da forma 'g(5) = '7' e'h(3,2) = 10' podem aparecer. Cada entrada nessa sequência precisa ser uma aplicação de uma função básica ou seguir de uma das entradas acima usando funções compostas, função recursiva primitiva ou μ-recursivas. Por exemplo, se f(x) = h(x,g(x)), então se 'f(5) = 3' for aparecer, termos como 'g(5) = 6' e 'h(3,6) = 3' devem aparecer em cima. A computação termina apenas se o termo final retorna o valor da função recursiva aplicada às entradas.

• Sistema de cadeia reescrito

Inclui algoritmo de Markov, que usa regras da gramática padrão para operar nos símbolos de strings; também há o Sistema pós-canônico.

• Máquina de registradores

É uma idealização teórica de um computador. Há uma grande quantidade de variantes. Na maioria delas, cada registrador pode guardar um número natural (de comprimento ilimitado), e as instruções são simples (e em pouca quantidade), ex.: apenas existem decremento (combinado com salto condicional) e incremento (e parada). A falta de infinito (ou crescimento dinâmico) armazenamento externo (visto em máquinas de Turing) pode ser entendido pela substituição dele pelas técnicas dos números de Gödel: o fato de que cada registrador guarda um número natural permite a possibilidade de representar um objeto complicado (como uma sequência ou matrizes, etc.) por um número natural gigante apropriado - sem ambiguidade de representação e interpretação.

• Máquina de Turing

Muito similar à máquina finita de estados, exceto que a entrada é provida por uma "fita" de execução, a qual a máquina de Turing pode ler, escrever, mover para trás e para frente com sua "cabeça de leitura". A "fita" é capaz de ter qualquer tamanho. A máquina de Turing é capaz de realizar cálculos complexos que podem ter duração arbitrária. Esse modelo é provavelmente o mais importante modelo da computação na ciência da computação, visto que ele simula a computação na ausência de recursos limitados pré-definidos.

• Máquina de Turing multi-fitas

Esta máquina é capaz de ter mais uma uma fita de entrada; além disso, pode haver múltiplas cabeças de leitura por fita. Surpreendentemente, qualquer computação que pode ser realizada por este tipo de máquina, também pode ser realizada por uma Máquina de Turing ordinária, apesar de que esta será mais lenta e requisitará mais região total da fita.

• P"

Como a Máquina de Turing, P" usa uma fita infinita de símbolos (sem acesso aleatório), e uma versão minimalística de instruções. Essas instruções, no entanto, são muito diferentes, portanto, diferentemente de máquinas de Turing, P'' não precisa manter um estado distinto, porque todas as funcionalidades de memória podem ser providas apenas pela fita. Ao invés de reescrever o símbolo atual, P" pode realizar um incremento na aritmética modular no símbolo. P" também tem um par de instruções para ciclos, averiguando o símbolo vazio. Apesar de sua natureza minimalística, P" tem se tornado a linguagem mãe de uma linguagem de programação implementada (de entretenimento) chamada Brainfuck.

Além dos modelos gerais, outros modelos computacionais mais simples são úteis para aplicações mais especiais e restritas. Expressões regulares, por exemplo, especificam padrões de strings em muitos contextos, desde software de produtividade tais como o Office, até linguagem de programação. Outro formalismo matemático equivalente a expressões regulares, autômatos finitos são usados em design de circuitos e alguns tipos de soluções de problemas. Gramáticas livre-de-contexto especificam a sintaxe da linguagem de programação. Autômatos com pilha não determinísticos é outro tipo de formalismo equivalente à gramáticas livre-de-contexto.

Diferentes modelos de computação têm habilidades de realizar tarefas diferentes. Um meio de medir o poder computacional de um modelo é estudar a classe de linguagens formais que o modelo pode gerar; desta maneira, a hierarquia de Chomsky é obtida.

Outros modelos restritos da computação incluem:

• Autômato finito determinístico' (AFD)'

Também é chamada de máquina de estados finita. Todos os instrumentos computacionais existentes nos dias de hoje podem ser modelados como uma máquina de estados finita, visto que todos os computadores reais operam com recursos finitos. Tal máquina tem um conjunto de estados, e um conjunto de transições de estados, que são afetados pela entrada. Alguns estados são definidos como "estados aceitáveis". A entrada alimenta a máquina um caractere por vez, e as transições de estado para o estado atual são comparadas com a entrada, e se há um estado correspondente, a máquina pode entrar em um novo estado. Se, ao final da entrada, a máquina estiver num "estado aceitável", então toda a entrada é aceita.

• Autômato finito não-determinístico (AFN)

É um outro modelo simples de computação, apesar de sua sequência de processos não ser univocamente determinada. Pode ser interpretada como tomando várias soluções de computação ao mesmo tempo através de estados finitos. Apesar disso, é demonstrável que qualquer AFN pode ser reduzido a um AFD equivalente.

• Autômato com pilha

Similar ao AFD, exceto que há uma pilha de execução que pode ter tamanho arbitrário indefinido. As transições de estado adicionalmente especificam se adiciona um símbolo à pilha ou removem-no. É muito mais poderoso que o AFD, visto que possui uma memória infinita em forma de pilha, apesar de apenas o elemento do topo ser acessível a qualquer momento.

Com os modelos computacionais em mãos, somos capazes de determinar quais são seus limites, ou seja, quais classes de linguagens eles aceitam?

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.

Enquanto M lê x, deve haver algum estado na máquina que é repetido no processo de leitura da primeira série de a's, visto que há (n+1) a's e somente n estados pelo Princípio da Casa dos Pombos. Chamemos este estado de S e seja d o número de a's que são lidos por M até que o estado S ocorra novamente. Sabemos, então, que ,nesta segunda ocorrência de S, podemos adicionar d (onde d > 0) a's e teremos novamente a ocorrência do estado S. Isso significa que uma string de tamanho (n+d+1) a's deve terminar no mesmo estado que uma string de tamanho (n+1) a's. Isso implica que se nossa máquina aceita x, ela deve também aceitar a string d (n+d+1) a's seguido por (n+1) b's, que não está na linguagem de strings que contém um número igual de a's e b's. Em outras palavras, M não pode corretamente diferenciar entre a string de números de a's iguais aos de b's e a string com (n+d+1) a's e (n+1) b's.

Sabemos, então, que esta linguagem não pode aceitar corretamente através de nenhuma máquina de finitos estados, e esta linguagem não é regular. Uma forma mais geral para este resultado é chamado de Lema do Bombeamento para linguagens regulares, que pode ser usado para mostrar que classes de linguagens amplas não podem ser reconhecidas por maquinas de finitos estados.

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.

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.

A máquina de Turing é um modelo de autômato extremamente poderoso. Tentativas de melhorar a definição de uma máquina de Turing para produzir um máquina mais poderosa tem levado a fracasso. Por exemplo, adicionar um "fita" extra na máquina, dando um 2-dimensão (or 3 or n-dimensão) de superfície infinita para trabalhar com, mas que pode ser simulada pela máquina de Turing padrão. Esses modelos, então, não são mais poderosos. De fato, a consequência da teoria de Church-Turing é que não há modelo razoável da computação que pode decidir linguagens que a máquina de Turing não pode.

A pergunta a ser feita é então: existe alguma linguagem que é recursivamente enumerável, mas não é recursiva? E mais, há linguagens que nem sequer são recursivamente enumeráveis?

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.

Isto é, o único caminho geral de saber com certeza se um dado programa parará quando executa sobre uma entrada específica em todos os casos é simplesmente executando e vendo se ele para. Se ele parar, então nós sabemos que para. Do contrário, você pode nunca saber se ele vai parar em algum momento no futuro. A linguagem que consiste de todas as descrições das máquinas de Turing pareada com todas as possibilidades de entrada sobre a qual tais máquinas vão parar, não é recursiva. O problema da parada é um problema não computável ou indecidível.

Uma extensão do problema da parada é o Teorema de Rice, que afirma que é indecidível (em geral) se a linguagem de uma dada máquina de Turing possui quaisquer propriedades específicas não triviais.

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.

Resultados subsequentes de autores como Alonzo Church incluem a demonstração de que uma função é recursiva se e somente se é computável por uma Máquina de Turing.

• Teoria de Algoritmos
• Teoria da Computação
• Máquina de Turing
• Problema da Parada