Número computável

Na matemática, particularmente na ciência da computação teórica e na lógica matemática, os números computáveis, também conhecidos como números recursivos ou reais computáveis, são os números reais que podem ser computados para qualquer precisão desejada por um algoritmo finito e que termina. Definições equivalentes podem ser dadas usando funções μ-recursivas, máquinas de Turing ou cálculo-λ como a representação formal de algoritmos. Os números computáveis formam um campo real fechado e podem ser usados no lugar de números reais, para muitos, mas não todos, fins de matemática.

Definição informal usando uma máquina de Turing como exemplo

A seguir, Marvin Minsky define os números a serem computados em uma maneira similar aos definidos por Alan Turing em 1936, ex.: como "sequências de dígitos interpretados como frações decimais" entre 0 e 1:

"Um número computável [é] aquele para o qual há uma máquina de Turing que, dado n em sua fita inicial, termina com o n-ésimo dígito desse número [codificados em sua fita]." (Minsky 1967:159)

As noções-chave na definição são (1) que algum n é especificado no início, (2) para qualquer n a computação só toma um número finito de passos, após o qual a máquina produz o resultado desejado e termina.

Uma forma alternativa para (2) – a máquina sucessivamente imprime todos dos n dígitos em sua fita, parando após imprimir o n-ésimo número – enfatiza a observação de Minsky: (3) que pelo uso de uma máquina de Turing, uma definição finita – na forma de tabela da máquina – está sendo utilizada para definir o que é uma sequência potencialmente-infinita de casas decimais.

Esta porém não é a definição moderna que só requer que um resultado seja preciso dentro de uma dada precisão qualquer. A definição informal acima está sujeita a um problema de arredondamento denominado dilema do construtor de tabelas, problema que não aparece na definição moderna.

Definição formal

Um número real a é dito ser computável se ele pode ser aproximado por uma função computável $f:\mathbb {N} \to \mathbb {Z}$ da seguinte maneira: dado qualquer inteiro n≥1, a função produz um inteiro $f(n)$ tal que:

${f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.$

Há duas definições semelhantes que são equivalentes:

• Existe uma função computável que, dado qualquer delimitador de erro racional positivo $\varepsilon$, produz um número racional r tal que $|r-a|\leq \varepsilon .$
• Há uma sequência de números racionais computáveis $q_{i}$ convergindo para $a$ tal que $|q_{i}-q_{i+1}|<2^{-i}\,$ para cada i.

Há uma outra definição equivalente de números computáveis via cortes de Dedekind computáveis. Um corte de Dedekind computável é uma função computável D que quando provido com um número racional r como entrada retorna D(r)=True ou D(r)=False, satisfazendo as seguintes condições:

$\exists rD(r)=True$

$\exists rD(r)=False$

$(D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;$

$D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;$

Um exemplo é dado por um programa D que define a raiz quadrada de 3. Assumindo que $q>0\;$ este é definido por:

$p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;$

$p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;$

Um número real é computável se e somente se houver um corte Dedekind computável D convergindo para ele. A função D é exclusiva para cada número irracional computável (embora, evidentemente, dois programas diferentes podem fornecer a mesma função).

Um número complexo é chamado computável se suas partes real e imaginária são computáveis.

Propriedades

Enquanto o conjunto de números reais é incontável, o conjunto de números computáveis é apenas contável e por conseguinte quase todos os números reais são não-computáveis. Os números computáveis podem ser contados atribuindo um número de Gödel para cada definição de máquina de Turing. Isso cria uma função dos naturais para os reais computáveis. Embora os números computáveis fazem parte de um campo ordenado, o conjunto de números de Gödel correspondentes à números computáveis não é em si computavelmente enumerável, porque não é eficientemente possível determinar quais números de Gödel correspondem à máquinas de Turing que produzem reais computáveis. Afim de produzir um real computável uma máquina de Turing deve computar uma função total, mas o problema de decisão correspondente está no Turing grau 0”. Assim o argumento de diagonalização de Cantor não pode ser usado para produzir incontáveis reais computáveis; no melhor, os reais formados por este método serão incomputáveis.

As operações aritméticas sobre números computáveis são elas próprias computáveis no sentido de que sempre que números reais a e b são computáveis, em seguida, os seguintes números reais também são computáveis: a + b, a - b, ab, e a/b se b é diferente de zero. Estas operações são, na verdade uniformemente computáveis; por exemplo, há uma máquina de Turing que na entrada (A, B, ε) produz uma saída r, onde A é a descrição de uma máquina de Turing aproximando a, B é a descrição de uma máquina de Turing aproximando b e r é uma aproximação ε de a+b.

Os números reais computáveis não compartilham todas as propriedades dos números reais usados na análise. Por exemplo, o menor limite superior de uma crescente e limitada sequência computável de números reais computáveis não precisa ser um número real computável (Bridgese Richman, 1987:58). Uma sequência com essa propriedade é conhecida como uma sequência Specker, por sua primeira construção ser devida a E. Specker (1949). Apesar da existência de contra-exemplos como estes, partes do cálculo e análise real podem ser desenvolvidas no campo dos números computáveis, levando ao estudo de análise computável.

A relação de ordem sobre os números computáveis não é computável. Não há nenhuma máquina de Turing que na entrada A (a descrição de uma máquina de Turing aproximando o número a) escreve na saída "SIM" se a > 0 e "NÃO" se a≤0. O motivo: suponha que a máquina descrita por A continua retornando 0 como aproximações . Não está claro quanto tempo esperar antes de decidir que a máquina nunca irá retornar uma aproximação que force a a ser positivo. Assim, a máquina acabará tendo que adivinhar que o número será igual a 0, a fim de produzir uma saída, a sequência pode mais tarde tornar-se diferente de 0. Esta ideia pode ser usada para mostrar que a máquina está incorreta em algumas sequências se ela calcula uma função total. Um problema semelhante ocorre quando os reais computáveis são representados como cortes de Dedekind. O mesmo vale para a relação de igualdade: o teste de igualdade não é computável.

Enquanto a relação de ordem total não é computável, a restrição de que a pares de números desiguais é computável. Ou seja, existe um programa que fornece entradas para duas máquinas de Turing A e B aproximando os números a e b, onde a ≠ b, e retorna se a < b ou a > b. É suficiente para usar aproximações-ε onde ε <| b - a | / 2; assim tomando ε cada vez menores (com o limite 0), uma pessoa eventualmente pode decidir se a < b ou a > b. Cada número computável é definível, mas não vice-versa. Existem muitos números reais definíveis, não-computáveis, incluindo:

• A representação binária do problema da parada (ou qualquer outro conjunto não-computável de números naturais).
• A constante de Chaitin, Ω, que é um tipo de número real que é Turing equivalente ao problema da parada.

Um número real é computável se e somente se o conjunto dos números naturais que ele representa
(quando escrito em binário e visto como uma função característica) é computável.

Sequências de dígitos e os espaços de Cantor e Baire

Em sua publicação original, Turing definiu números computáveis da seguinte forma:

Um número real é computável se a sua sequência numérica pode ser produzida por algum algoritmo ou máquina de Turing. O algoritmo tem um inteiro n≥1 como entrada e produz o n-ésimo dígito da expansão decimal do número real como saída.

(Note que a expansão decimal de a só se refere aos dígitos após o ponto decimal.)

Turing estava ciente de que esta definição é equivalente à definição da aproximação- ε dada acima. O argumento procede assim: se um número é computável no sentido de Turing, então também é computável no sentido ε: se n>log_10⁡(1/ε), então os primeiros n dígitos da expansão decimal para a proporciona uma aproximação-ε de a. Para conversar, nós escolhemos um número real a ε computável e geramos aproximações cada vez mais precisas até que o n-ésimo dígito após o ponto decimal é conhecido. Isso sempre gera uma expansão decimal igual a a, mas pode indevidamente resultar em uma sequência infinita de 9s em qual caso ela deve ter um finita (e, portanto, computável) e adequada expansão decimal.

A menos que certas propriedades topológicas dos números reais sejam relevantes, muitas vezes é mais conveniente lidar com elementos de 2^w (funções valorizadas total 0,1) em vez de números reais [0,1]. Os membros do 2^w podem ser identificados com expansões decimais binárias mas desde que as expansões decimais d_1 d_2…d_n 0111… e d_1 d_2…d_n 10 denotem o mesmo número real. O intervalo [0,1] só pode ser bijetivamente (e homeomorficamente sob a topologia de um subconjunto) identificado com o subconjunto de 2^w que não termina em cadeias de apenas 1s.

Note que esta propriedade das expansões decimais significa que é impossível identificar de maneira eficiente números reais computáveis definidos em termos de uma expansão decimal e os definidos no sentido da aproximação- ε. Hirst mostrou que não existe algoritmo que recebe como entrada a descrição de uma máquina de Turing que produz aproximações-ε para o número computável a, e produz como saída uma máquina de Turing que enumera os dígitos de a no sentido da definição de Turing (ver Hirst 2007) . Da mesma forma, significa que as operações aritméticas sobre os reais computáveis não são tão eficazes em suas representações decimais quanto quando estão adicionando números decimais; a fim de produzir um dígito, pode ser necessário olhar arbitrariamente longe para a direita para determinar se há um carry para a localização atual. Esta falta de uniformidade é um dos motivos que a definição contemporânea de números computáveis usa aproximações- ε ao invés de expansões decimais.

No entanto, a partir de uma perspectiva computacional ou de medidas teórica as duas estruturas 2^w e [0,1] são essencialmente idênticas. E teóricos da computabilidade muitas vezes se referem aos membros de 2^w como reais. Enquanto [0,1] 2^w é totalmente desconexos para perguntas sobre classes π_1^0 ou aleatoriedade, é muito menos confuso trabalhar em 2^w.

Elementos de w^w às vezes são também chamados de reais, e embora contenham uma imagem homeomórfica de Rw^w além de serem totalmente desconexos, não são nem localmente compactos. Isso leva a diferenças genuínas nas propriedades computacionais. Por exemplo, x∈R satisfazendo ∀(n∈w)φ (x,n) com φ (x, n) livre de quantificador deve ser computável enquanto o singular x∈w^w satisfazendo uma fórmula universal pode ser arbitrariamente alto na hierarquia hiperaritmética.

Pode-se usar números computáveis ao invés dos reais?

Os números computáveis incluem muitos dos específicos números reais que aparecem na prática, incluindo todos os números algébricos, bem como e, π, e muitos outros números transcendentais. Embora os reais computável exaurem os reais acima podemos calcular ou aproximar, a suposição de que todos os reais são computáveis leva à conclusões substancialmente diferentes sobre os números reais. A pergunta naturalmente surge de saber se é possível descartar todo o conjunto dos reais e usar apenas números computáveis para toda a matemática. Esta ideia é atraente do ponto de vista construtivista, e foi perseguida pelo que Bishop e Richman chamaram de a escola Russa da matemática construtiva.

Para realmente desenvolver a análise sobre números computáveis, alguns cuidados devem ser tomados. Por exemplo, se alguém usa a definição clássica de uma sequência, o conjunto de números computáveis não é fechado sob a operação básica de retirar o supremo de uma sequência limitada (por exemplo, considere uma sequência Specker). Esta dificuldade é notada quando se considera apenas sequências que contém um módulo de convergência computável . A teoria matemática resultante é chamada de análise da computabilidade.

Implementação

Existem alguns pacotes de computador que trabalham com números reais computáveis, representando os números reais como aproximações computáveis de programas. Um exemplo é o pacote RealLib (home page reallib).

Referências

• Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299. This paper describes the development of the calculus over the computable number field.
• Errett Bishop and Douglas Bridges, Constructive Analysis, Springer, 1985, ISBN 0387150668
• Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
• Jeffry L. Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics, 55, (2007) 303–316.
• Marvin Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. His chapter §9 "The Computable Real Numbers" expands on the topics of this article.
• E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic, 14 (1949) pp. 145–158
• Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2 42 (1): 230–65, 1937, doi:10.1112/plms/s2-42.1.230(and Turing, A.M. (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction", Proceedings of the London Mathematical Society, 2 43 (6): 544–6, 1937,doi:10.1112/plms/s2-43.6.544). Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
• Klaus Weihrauch 2000, Computable analysis, Texts in theoretical computer science, Springer, ISBN 3540668179. §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.
• Klaus Weihrauch, A simple introduction to computable analysis