Número computável - Computable number

π pode ser calculado com precisão arbitrária, enquanto quase todos os números reais não são computáveis.

Em matemática , os números computáveis são os números reais que podem ser calculados com qualquer precisão desejada por um algoritmo de terminação finito . Eles também são conhecidos como números recursivos , números efetivos (vanDerHoeven) ou reais computáveis ou reais recursivos .

Definições equivalentes podem ser fornecidas 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 dos números reais para muitos, mas não todos, propósitos matemáticos.

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

A seguir, Marvin Minsky define os números a serem calculados de maneira semelhante àqueles definidos por Alan Turing em 1936; ou seja, como "sequências de dígitos interpretados como frações decimais" entre 0 e 1:

Um número calculável [representa] um para o qual existe uma máquina de Turing que, dado n sobre a sua fita inicial, termina com o n ésimo dígito desse número [codificado na sua fita].

As noções-chave na definição são (1) que algum n é especificado no início, (2) para qualquer n o cálculo leva apenas um número finito de etapas, após as quais a máquina produz a saída desejada e termina.

Uma forma alternativa de (2) - a máquina sucessivamente imprime todos n dos dígitos em sua fita, parando depois de imprimir o n º - enfatiza a observação de Minsky: (3) Que por uso de uma máquina de Turing, um finito definição - sob a forma da mesa da máquina - está sendo usado para definir o que é uma seqüência potencialmente infinita de dígitos decimais.

No entanto, esta não é a definição moderna que requer apenas que o resultado seja preciso dentro de uma determinada precisão. A definição informal acima está sujeita a um problema de arredondamento chamado dilema do fabricante de mesa, ao passo que a definição moderna não está.

Definição formal

Um número real a é computável se puder ser aproximado por alguma função computável da seguinte maneira: dado qualquer número inteiro positivo n , a função produz um número inteiro f ( n ) tal que:

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

  • Existe uma função computável que, dado qualquer limite de erro racional positivo , produz um número racional r tal que
  • Existe uma sequência computável de números racionais convergindo para tal que para cada i .

Há outra definição equivalente de números computáveis ​​por meio de cortes Dedekind computáveis . Um corte de Dedekind computável é uma função computável que, quando fornecida com um número racional como retorno de entrada ou , satisfaz as seguintes condições:

Um exemplo é dado por um programa D que define a raiz cúbica de 3. Supondo que isso seja definido por:

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

Um número complexo é denominado computável se suas partes reais e imaginárias são computáveis.

Propriedades

Não computávelmente enumerável

Atribuir um número de Gödel a cada definição de máquina de Turing produz um subconjunto dos números naturais correspondentes aos números computáveis ​​e identifica uma surjeção dos números computáveis. Existem apenas muitas máquinas de Turing contáveis, mostrando que os números computáveis ​​são subcontáveis . O conjunto desses números de Gödel, entretanto, não é computávelmente enumerável (e conseqüentemente, nem são subconjuntos que são definidos em termos dele). Isso ocorre porque não existe um algoritmo para determinar quais números de Gödel correspondem às máquinas de Turing que produzem reais computáveis. Para produzir um real computável, uma máquina de Turing deve calcular uma função total , mas o problema de decisão correspondente está no grau de Turing 0 ′ ′ . Conseqüentemente, não há função computável sobrejetiva dos números naturais para os reais computáveis, e o argumento diagonal de Cantor não pode ser usado construtivamente para demonstrar incontáveis ​​muitos deles.

Enquanto o conjunto de números reais é incontável , o conjunto de números computáveis ​​é classicamente contável e, portanto, quase todos os números reais não são computáveis. Aqui, para qualquer dado número computável, o princípio de ordenação do poço fornece que existe um elemento mínimo que corresponde a e, portanto, existe um subconjunto que consiste nos elementos mínimos, nos quais o mapa é uma bijeção . O inverso dessa bijeção é uma injeção nos números naturais dos números computáveis, provando que eles são contáveis. Mas, novamente, este subconjunto não é computável, embora os reais computáveis ​​sejam ordenados.

Propriedades como um campo

As operações aritméticas sobre números computáveis são eles próprios computável 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 , ab , ab , e a / b se b é diferente de zero. Na verdade, essas operações são computáveis ​​de maneira uniforme ; por exemplo, há uma máquina de Turing que na entrada ( A , B , ) produz a saída r , onde A é a descrição de uma máquina de Turing que se aproxima de a , B é a descrição de uma máquina de Turing que se aproxima de b e r é uma aproximação de a + b .

O fato de que números reais computáveis ​​formam um campo foi provado pela primeira vez por Henry Gordon Rice em 1954 (Rice 1954).

Os reais computáveis, entretanto, não formam um campo computável , porque a definição de um campo computável requer igualdade efetiva.

Não computabilidade do pedido

A relação de ordem nos números computáveis ​​não é computável. Seja A a descrição de uma máquina de Turing que se aproxima do número . Então, não há máquina de Turing que na entrada A produza "SIM" se e "NÃO" se. Para ver por que, suponha que a máquina descrita por A continue gerando 0 como aproximações. Não está claro quanto tempo esperar antes de decidir que a máquina nunca produzirá uma aproximação que force a a ser positivo. Assim, a máquina eventualmente terá 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. Essa ideia pode ser usada para mostrar que a máquina está incorreta em algumas sequências se computar 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.

Embora a relação de ordem completa não seja computável, sua restrição a pares de números desiguais é computável. Ou seja, não é um programa que recebe como entrada duas máquinas Turing A e B a aproximação de números um e b , onde umb , e saídas se ou é suficiente a utilização de ε -approximations onde assim, tomando cada vez mais pequeno ε (0 aproximando ), eventualmente pode-se decidir se ou

Outras propriedades

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 sequência computável limitada crescente de números reais computáveis ​​não precisa ser um número real computável (Bridges e Richman, 1987: 58). Uma sequência com esta propriedade é conhecida como sequência Specker , pois a primeira construção é devida a E. Specker (1949). Apesar da existência de contra-exemplos como esses, partes do cálculo e da análise real podem ser desenvolvidas no campo dos números computáveis, levando ao estudo da análise computável .

Cada número computável é definível , mas não vice-versa. Existem muitos números reais definíveis e não computáveis, incluindo:

Ambos os exemplos de fato definem um conjunto infinito de números definíveis e não computáveis, um para cada máquina de Turing universal . Um número real é computável se e somente se o conjunto de números naturais que ele representa (quando escrito em binário e visto como uma função característica) é computável.

Cada número computável é aritmético .

O conjunto de números reais computáveis ​​(assim como todo subconjunto contável e densamente ordenado de reais computáveis ​​sem extremidades) é isomórfico de ordem ao conjunto de números racionais.

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

O artigo original de Turing definiu os números computáveis ​​da seguinte forma:

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

(A expansão decimal de a refere-se apenas aos dígitos após a vírgula decimal.)

Turing estava ciente de que essa definição é equivalente à definição de aproximação dada acima. O argumento procede da seguinte forma: se um número é computável no sentido de Turing, então também é computável no sentido: se , então os primeiros n dígitos da expansão decimal para a fornecem uma aproximação de a . Para o contrário, nós escolhemos um computável número real um e gerar aproximações cada vez mais precisos até que o n º dígitos depois do ponto decimal é certa. Isso sempre gera uma expansão decimal igual a a, mas pode terminar incorretamente em uma sequência infinita de 9's, caso em que deve ter uma expansão decimal adequada finita (e, portanto, computável).

A menos que certas propriedades topológicas dos números reais sejam relevantes, é freqüentemente mais conveniente lidar com elementos de (funções com valor total de 0,1) em vez de números reais em . Os membros podem ser identificados com expansões decimais binárias mas desde que as expansões decimais e denotam o mesmo número real o intervalo só pode ser bijectively (e homeomorphically sob a topologia subconjunto) identificado com o subconjunto de não terminando em todos os 1 de.

Observe que esta propriedade das expansões decimais significa que é impossível identificar efetivamente números reais computáveis ​​definidos em termos de uma expansão decimal e aqueles definidos no sentido de aproximação. Hirst mostrou que não há algoritmo que tome como entrada a descrição de uma máquina de Turing que produz aproximações para o número computável a e produza 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 em reais computáveis ​​não são eficazes em suas representações decimais como ao adicionar números decimais, a fim de produzir um dígito, pode ser necessário olhar arbitrariamente para a direita para determinar se há um transporte para o localização atual. Essa falta de uniformidade é um dos motivos pelos quais a definição contemporânea de números computáveis ​​usa aproximações em vez de expansões decimais.

No entanto, a partir de um modelo computacional ou teórico medida em perspectiva das duas estruturas e são essencialmente idênticas, e teóricos computabilidade muitas vezes referir-se a membros de como reais. Embora esteja totalmente desconectado , para questões sobre classes ou aleatoriedade é muito menos complicado de trabalhar .

Os elementos de às vezes também são chamados de reais e, embora contenham uma imagem homeomórfica de , além de estar totalmente desconectado, não é nem mesmo localmente compacto. Isso leva a diferenças genuínas nas propriedades computacionais. Por exemplo, a satisfação com o quantificador livre deve ser computável, enquanto o único que satisfaz uma fórmula universal pode ser arbitrariamente alto na hierarquia hiperaritmética .

Use no lugar dos reais

Os números computáveis ​​incluem os números reais específicos que aparecem na prática, incluindo todos os números algébricos reais , bem como e , π e muitos outros números transcendentais . Embora os reais computáveis ​​esgotem aqueles reais que podemos calcular ou aproximar, a suposição de que todos os reais são computáveis ​​leva a conclusões substancialmente diferentes sobre os números reais. A questão que surge naturalmente é se é possível descartar o conjunto completo de reais e usar números computáveis ​​para toda a matemática. Essa ideia é atraente do ponto de vista construtivista e foi perseguida pelo que Bishop e Richman chamam de escola russa de matemática construtiva.

Para realmente desenvolver análises 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 tomar o supremo de uma sequência limitada (por exemplo, considere uma sequência Specker , consulte a seção acima). Esta dificuldade é abordada considerando apenas sequências que têm um módulo de convergência computável . A teoria matemática resultante é chamada de análise computável .

Implementação

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

Veja também

Referências

  1. ^ Minsky, Marvin (1967). "9. Os Números Reais Computáveis". Computação: Máquinas Finitas e Infinitas . Prentice-Hall. ISBN 0-13-165563-9. OCLC  0131655639 .