Computabilidade - Computability

Computabilidade é a capacidade de resolver um problema de maneira eficaz. É um tópico chave do campo da teoria da computabilidade dentro da lógica matemática e da teoria da computação dentro da ciência da computação . A computabilidade de um problema está intimamente ligada à existência de um algoritmo para resolver o problema.

Os modelos de computabilidade mais amplamente estudados são as funções Turing-computáveis e μ-recursivas , e o cálculo lambda , todos os quais têm poder computacionalmente equivalente. Outras formas de computabilidade também são estudadas: noções de computabilidade mais fracas do que as máquinas de Turing são estudadas na teoria dos autômatos , enquanto as noções de computabilidade mais fortes do que as máquinas de Turing são estudadas no campo da hipercomputação .

Problemas

Uma ideia central em computabilidade é a de um problema ( computacional ) , que é uma tarefa cuja computabilidade pode ser explorada.

Existem dois tipos principais de problemas:

Um problema de decisão correções de um conjunto S , o que pode ser um conjunto de cordas, números naturais, ou outros objetos retirados de um conjunto maior U . Um determinado exemplo do problema é o de decidir, uma vez um elemento de retorno de U , se U é em S . Por exemplo, seja U o conjunto de números naturais e S o conjunto de números primos. O problema de decisão correspondente corresponde ao teste de primalidade .
Um problema função consiste de uma função F a partir de um conjunto L de um conjunto V . Um exemplo do problema é a computação, dado um elemento u em L , o elemento que corresponde f ( u ) em V . Por exemplo, U e V podem ser o conjunto de todas as strings binárias finitas e f pode pegar uma string e retornar a string obtida invertendo os dígitos da entrada (então f (0101) = 1010).

Outros tipos de problemas incluem problemas de pesquisa e problemas de otimização .

Um dos objetivos da teoria da computabilidade é determinar quais problemas, ou classes de problemas, podem ser resolvidos em cada modelo de computação.

Modelos formais de computação

Um modelo de computação é uma descrição formal de um tipo particular de processo computacional. A descrição geralmente assume a forma de uma máquina abstrata destinada a realizar a tarefa em questão. Modelos gerais de computação equivalentes a uma máquina de Turing (ver tese de Church-Turing ) incluem:

Cálculo lambda: Um cálculo consiste em uma expressão lambda inicial (ou duas se você quiser separar a função e sua entrada) mais uma sequência finita de termos lambda, cada um deduzido do termo anterior por uma aplicação de redução beta .
Lógica combinatória: Um conceito que tem muitas semelhanças com -calculus, mas também existem diferenças importantes (por exemplo, o combinador de ponto fixo Y tem forma normal em lógica combinatória, mas não em -calculus). A lógica combinatória foi desenvolvida com grandes ambições: compreender a natureza dos paradoxos, tornar os fundamentos da matemática mais econômicos (conceitualmente), eliminar a noção de variáveis (esclarecendo assim seu papel na matemática). ${\ displaystyle \ lambda}$ ${\ displaystyle \ lambda}$
funções μ-recursivas: Um cálculo consiste em uma função μ-recursiva, ou seja, sua sequência de definição, quaisquer valores de entrada e uma sequência de funções recursivas que aparecem na sequência de definição com entradas e saídas. Assim, se na sequência de definição de uma função recursiva $f (x)$ a funções $g (x)$ e $h (x, y)$ aparecem, em seguida termos da forma $g (5) = 7$ ou $H (3,2) = 10$ pode aparecer. Cada entrada nesta sequência precisa ser uma aplicação de uma função básica ou seguir as entradas acima usando composição , recursão primitiva ou recursão µ . Por exemplo, se $f (x) = h (x, g (x))$ , então para $f (5) = 3$ aparecer, termos como $g (5) = 6$ e $h (5,6) = 3$ devem ocorrer acima. O cálculo termina apenas se o termo final fornecer o valor da função recursiva aplicada às entradas.
Sistemas de reescrita de strings: Inclui algoritmos de Markov , que usam regras semelhantes a gramática para operar em cadeias de símbolos; também Post sistema canônico .
Maquina registradora: Uma idealização teórica de um computador. Existem várias variantes. Na maioria deles, cada registro pode conter um número natural (de tamanho ilimitado), e as instruções são simples (e poucos em número), por exemplo, apenas decrementação (combinada com salto condicional) e incremento existem (e parada). A falta de armazenamento externo infinito (ou crescendo dinamicamente) (visto nas máquinas de Turing) pode ser compreendida substituindo seu papel por técnicas de numeração de Gödel : o fato de que cada registro contém um número natural permite a possibilidade de representar uma coisa complicada (por exemplo, um sequência, ou uma matriz, etc.) por um grande número natural apropriado - não ambigüidade de representação e interpretação pode ser estabelecida por fundamentos teóricos de número dessas técnicas.
Máquina de Turing: Também semelhante à máquina de estado finito, exceto que a entrada é fornecida em uma "fita" de execução, da qual a máquina de Turing pode ler, gravar ou mover para frente e para trás além de sua "cabeça" de leitura / gravação. A fita pode crescer até um tamanho arbitrário. A máquina de Turing é capaz de realizar cálculos complexos que podem ter duração arbitrária. Este modelo é talvez o modelo de computação mais importante em ciência da computação, pois simula a computação na ausência de limites de recursos predefinidos.
Máquina de Turing Multitape: Aqui, pode haver mais de uma fita; além disso, pode haver várias cabeças por fita. Surpreendentemente, qualquer cálculo que possa ser executado por esse tipo de máquina também pode ser executado por uma máquina de Turing comum, embora a última possa ser mais lenta ou exigir uma região total maior de sua fita.
P ′ ′: Como as máquinas de Turing, P ′ ′ usa uma fita infinita de símbolos (sem acesso aleatório) e um conjunto de instruções bastante minimalista. Mas essas instruções são muito diferentes, portanto, ao contrário das máquinas de Turing, P ′ ′ não precisa manter um estado distinto, porque todas as funcionalidades “semelhantes à memória” podem ser fornecidas apenas pela fita. Em vez de reescrever o símbolo atual, ele pode realizar uma incrementação aritmética modular nele. P ′ ′ também tem um par de instruções para um ciclo, inspecionando o símbolo em branco. Apesar de sua natureza minimalista, tornou-se a linguagem formal dos pais de uma linguagem de programação implementada e (para entretenimento) usada chamada Brainfuck .

Além dos modelos computacionais gerais, alguns modelos computacionais mais simples são úteis para aplicativos especiais restritos. Expressões regulares , por exemplo, especificam padrões de string em muitos contextos, de software de produtividade de escritório a linguagens de programação . Outro formalismo matematicamente equivalente às expressões regulares, os autômatos finitos são usados no projeto de circuitos e em alguns tipos de solução de problemas. Gramáticas livres de contexto especificam a sintaxe da linguagem de programação. Autômatos pushdown não determinísticos são outro formalismo equivalente a gramáticas livres de contexto.

Diferentes modelos de computação têm a capacidade de realizar diferentes tarefas. Uma maneira de medir o poder de um modelo computacional é estudar a classe de linguagens formais que o modelo pode gerar; desta forma é obtida a hierarquia de línguas de Chomsky .

Outros modelos restritos de computação incluem:

Autômato finito determinístico (DFA): Também chamada de máquina de estado finito. Todos os dispositivos de computação reais existentes hoje podem ser modelados como uma máquina de estado finito, já que todos os computadores reais operam com recursos finitos. Essa máquina tem um conjunto de estados e um conjunto de transições de estado que são afetados pelo fluxo de entrada. Certos estados são definidos para aceitar estados. Um fluxo de entrada é alimentado na máquina, um caractere por vez, e as transições de estado para o estado atual são comparadas ao fluxo de entrada e, se houver uma transição correspondente, a máquina pode entrar em um novo estado. Se no final do fluxo de entrada a máquina estiver em um estado de aceitação, todo o fluxo de entrada será aceito.
Autômato finito não determinístico (NFA): Outro modelo simples de computação, embora sua sequência de processamento não seja determinada de maneira única. Pode ser interpretado como vários caminhos de computação simultaneamente por meio de um número finito de estados. No entanto, é possível provar que qualquer NFA é redutível a um DFA equivalente.
Autômato pushdown: Semelhante à máquina de estado finito, exceto que tem disponível uma pilha de execução, que pode crescer até um tamanho arbitrário. As transições de estado especificam adicionalmente se deve adicionar um símbolo à pilha ou remover um símbolo da pilha. É mais poderoso do que um DFA devido à sua pilha de memória infinita, embora apenas o elemento superior da pilha esteja acessível a qualquer momento.

Poder dos autômatos

Com esses modelos computacionais em mãos, podemos determinar quais são seus limites. Ou seja, quais classes de línguas eles podem aceitar?

Poder das máquinas de estado finito

Os cientistas da computação chamam qualquer linguagem que pode ser aceita por uma máquina de estado finito de linguagem regular . Devido à restrição de que o número de estados possíveis em uma máquina de estados finitos é finito, podemos ver que, para encontrar uma linguagem que não seja regular, devemos construir uma linguagem que exigiria um número infinito de estados.

Um exemplo de tal linguagem é o conjunto de todas as strings consistindo nas letras 'a' e 'b' que contêm um número igual da letra 'a' e 'b'. Para ver por que essa linguagem não pode ser reconhecida corretamente por uma máquina de estados finitos, suponha primeiro que essa máquina M exista. M deve ter algum número de estados n . Agora considere a string x consistindo em 'a's seguido por ' b's. ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + 1)}$

Conforme M lê em x , deve haver algum estado na máquina que é repetido conforme ela é lida na primeira série de 'a's, uma vez que há ' a's e apenas n estados pelo princípio do escaninho . Chame esse estado de S e, além disso, seja d o número de 'a's que nossa máquina leu para ir da primeira ocorrência de S a alguma ocorrência subsequente durante a sequência' a '. Sabemos, então, que naquela segunda ocorrência de S , podemos adicionar um adicional d (onde ) 'um e nós será novamente no estado S . Isso significa que sabemos que uma string de 'a's deve terminar no mesmo estado que a string de ' a's. Isso implica que, se nossa máquina aceita x , ela também deve aceitar a string de 'a's seguida por ' b's, que não está na linguagem de strings contendo um número igual de 'a's e' b's. Em outras palavras, M não pode distinguir corretamente entre uma string de número igual de 'a's e' b's e uma string com 'a's e ' b's. ${\ displaystyle (n + 1)}$ ${\ displaystyle d> 0}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle (n + 1)}$ ${\ displaystyle (n + d + 1)}$ ${\ displaystyle n + 1}$

Sabemos, portanto, que essa linguagem não pode ser aceita corretamente por nenhuma máquina de estado finito e, portanto, não é uma linguagem regular. Uma forma mais geral desse resultado é chamada de lema do Pumping para linguagens regulares , que pode ser usado para mostrar que classes amplas de linguagens não podem ser reconhecidas por uma máquina de estados finitos.

Poder dos autômatos pushdown

Os cientistas da computação definem uma linguagem que pode ser aceita por um autômato pushdown como uma linguagem livre de contexto , que pode ser especificada como uma gramática livre de contexto . A linguagem que consiste em strings com números iguais de 'a's e' b's, que mostramos não era uma linguagem regular, pode ser decidida por um autômato push-down. Além disso, em geral, um autômato push-down pode se comportar como uma máquina de estado finito, portanto, pode decidir qualquer linguagem que seja regular. Este modelo de computação é, portanto, estritamente mais poderoso do que as máquinas de estado finito.

No entanto, verifica-se que existem linguagens que também não podem ser decididas pelo autômato push-down. O resultado é semelhante ao das expressões regulares e não será detalhado aqui. Existe um lema de Pumping para linguagens livres de contexto . Um exemplo de tal linguagem é o conjunto de números primos.

Poder das máquinas de Turing

As máquinas de Turing podem decidir qualquer linguagem livre de contexto, além das linguagens não decidíveis por um autômato push-down, como a linguagem que consiste em números primos. É, portanto, um modelo de computação estritamente mais poderoso.

Como as máquinas de Turing têm a capacidade de "fazer backup" em sua fita de entrada, é possível que uma máquina de Turing funcione por um longo tempo de uma maneira que não é possível com os outros modelos de computação descritos anteriormente. É possível construir uma máquina de Turing que nunca irá terminar de funcionar (parar) em algumas entradas. Dizemos que uma máquina de Turing pode decidir uma linguagem se eventualmente parar em todas as entradas e dar uma resposta. Uma linguagem que pode ser assim decidida é chamada de linguagem recursiva . Podemos ainda descrever as máquinas de Turing que eventualmente irão parar e dar uma resposta para qualquer entrada em uma linguagem, mas que podem funcionar indefinidamente para strings de entrada que não estão na linguagem. Essas máquinas de Turing poderiam nos dizer que uma determinada string está na linguagem, mas nunca podemos ter certeza, com base em seu comportamento, de que uma determinada string não está em uma linguagem, uma vez que pode ser executada para sempre nesse caso. Uma linguagem aceita por tal máquina de Turing é chamada de linguagem recursivamente enumerável .

A máquina de Turing, ao que parece, é um modelo de autômato extremamente poderoso. As tentativas de alterar a definição de uma máquina de Turing para produzir uma máquina mais poderosa falharam surpreendentemente. Por exemplo, adicionar uma fita extra à máquina de Turing, dando a ela uma superfície infinita bidimensional (ou tridimensional) para trabalhar pode ser simulado por uma máquina de Turing com a fita unidimensional básica. Esses modelos, portanto, não são mais poderosos. Na verdade, uma consequência da tese de Church-Turing é que não existe um modelo razoável de computação que pode decidir linguagens que não podem ser decididas por uma máquina de Turing.

A questão a fazer então é: existem linguagens que são recursivamente enumeráveis, mas não recursivas? E, além disso, existem linguagens que não são sequer recursivamente enumeráveis?

O problema da parada

O problema da parada é um dos problemas mais famosos da ciência da computação, porque tem profundas implicações na teoria da computabilidade e em como usamos os computadores na prática diária. O problema pode ser formulado:

Dada a descrição de uma máquina de Turing e sua entrada inicial, determine se o programa, quando executado nesta entrada, sempre para (é concluído). A alternativa é que ele funcione para sempre sem parar.

Aqui, não estamos fazendo uma pergunta simples sobre um número primo ou um palíndromo, mas, em vez disso, viramos o jogo e pedimos a uma máquina de Turing que responda a uma pergunta sobre outra máquina de Turing. Pode ser mostrado (ver artigo principal: Problema de parada ) que não é possível construir uma máquina de Turing que possa responder a esta pergunta em todos os casos.

Ou seja, a única maneira geral de saber com certeza se um determinado programa irá parar em uma determinada entrada em todos os casos é simplesmente executá-lo e ver se ele pára. Se parar, você sabe que para. Se não parar, no entanto, você nunca saberá se acabará parando. A linguagem que consiste em todas as descrições da máquina de Turing emparelhadas com todos os fluxos de entrada possíveis nos quais essas máquinas de Turing irão eventualmente parar, não é recursiva. O problema da parada é, portanto, denominado não computável ou indecidível .

Uma extensão do problema da parada é chamada de teorema de Rice , que afirma que é indecidível (em geral) se uma dada linguagem possui qualquer propriedade não trivial específica.

Além de linguagens recursivamente enumeráveis

O problema da parada é fácil de resolver, entretanto, se permitirmos que a máquina de Turing que decide isso possa funcionar para sempre quando receber uma entrada que é uma representação de uma máquina de Turing que não para. A linguagem interrompida é, portanto, recursivamente enumerável. No entanto, é possível construir linguagens que nem mesmo são recursivamente enumeráveis.

Um exemplo simples de tal linguagem é o complemento da linguagem hesitante; essa é a linguagem que consiste em todas as máquinas de Turing emparelhadas com strings de entrada, onde as máquinas de Turing não param em sua entrada. Para ver que essa linguagem não é recursivamente enumerável, imagine que construímos uma máquina de Turing M que é capaz de dar uma resposta definitiva para todas essas máquinas de Turing, mas que pode funcionar para sempre em qualquer máquina de Turing que eventualmente pare. Podemos então construir outra máquina de Turing que simule a operação dessa máquina, além de simular diretamente a execução da máquina fornecida na entrada, intercalando a execução dos dois programas. Como a simulação direta acabará parando se o programa que está simulando parar, e como, por suposição, a simulação de M acabará parando se o programa de entrada nunca parasse, sabemos que eventualmente terá uma de suas versões paralelas interrompida. é, portanto, um decisor para o problema da parada. Já mostramos, no entanto, que o problema da parada é indecidível. Temos uma contradição e, portanto, mostramos que nossa suposição de que M existe é incorreta. O complemento da linguagem de parada não é, portanto, recursivamente enumerável. ${\ displaystyle M '}$ ${\ displaystyle M '}$ ${\ displaystyle M '}$

Modelos baseados em simultaneidade

Vários modelos computacionais baseados em concorrência foram desenvolvidos, incluindo a máquina de acesso aleatório paralela e a rede de Petri . Esses modelos de computação concorrente ainda não implementam nenhuma função matemática que não possa ser implementada por máquinas de Turing.

Modelos mais fortes de computação

A tese de Church-Turing conjectura que não existe um modelo eficaz de computação que possa computar mais funções matemáticas do que uma máquina de Turing. Os cientistas da computação imaginaram muitas variedades de hipercomputadores , modelos de computação que vão além da computabilidade de Turing.

Execução infinita

Imagine uma máquina onde cada etapa do cálculo requer metade do tempo da etapa anterior (e, com sorte, metade da energia da etapa anterior ...). Se normalizarmos para 1/2 unidade de tempo a quantidade de tempo necessária para a primeira etapa (e para 1/2 unidade de energia a quantidade de energia necessária para a primeira etapa ...), a execução exigiria

{\ displaystyle 1 = \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {2 ^ {n}}} = {\ frac {1} {2}} + {\ frac {1} {4}} + {\ frac {1} {8}} + {\ frac {1} {16}} + \ cdots}

unidade de tempo (e 1 unidade de energia ...) para funcionar. Esta série infinita converge para 1, o que significa que esta máquina Zeno pode executar um número infinito de etapas em 1 unidade de tempo (usando 1 unidade de energia ...). Esta máquina é capaz de resolver o problema de parada simulando diretamente a execução da máquina em questão. Por extensão, qualquer série infinita convergente [deve ser provavelmente infinita] funcionaria. Supondo que a série infinita converge para um valor n , a máquina de Zeno completaria uma execução infinita contável em n unidades de tempo.

Maquinas oracle

As chamadas máquinas Oracle têm acesso a vários "oráculos" que fornecem a solução para problemas específicos indecidíveis. Por exemplo, a máquina de Turing pode ter um "oráculo de parada" que responde imediatamente se uma dada máquina de Turing irá parar em um dado input. Essas máquinas são um tópico central de estudo na teoria da recursão .

Limites de hiper-computação

Mesmo essas máquinas, que aparentemente representam o limite dos autômatos que poderíamos imaginar, esbarram em suas próprias limitações. Embora cada um deles possa resolver o problema da parada para uma máquina de Turing, eles não podem resolver sua própria versão do problema da parada. Por exemplo, uma máquina Oracle não pode responder à pergunta se uma determinada máquina Oracle algum dia irá parar.

Veja também

Referências

Michael Sipser (1997). Introdução à Teoria da Computação . Publicação PWS. ISBN 0-534-94728-X. Parte Dois: Teoria da Computabilidade, Capítulos 3-6, pp. 123-222.
Christos Papadimitriou (1993). Complexidade computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1. Capítulo 3: Computabilidade, pp. 57-70.
S. Barry Cooper (2004). Teoria da Computabilidade (1ª ed.). Chapman & Hall / CRC. ISBN 978-1-58488-237-4.

Languages

In other projects