Número computável - Computable number
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 um ≠ b , 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:
- qualquer número que codifica a solução do problema da parada (ou qualquer outro problema indecidível ) de acordo com um esquema de codificação escolhido.
- Constante de chaitin , que é um tipo de número real que é Turing equivalente ao problema da parada.
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
- ^ 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 .
- Aberth, Oliver (1968). "Análise no campo de números computáveis". Journal of the Association for Computing Machinery . 15 (2): 276–299. doi : 10.1145 / 321450.321460 . S2CID 18135005 . Este artigo descreve o desenvolvimento do cálculo sobre o campo de números computáveis.
- Bispo, Errett; Bridges, Douglas (1985). Análise construtiva . Springer. ISBN 0-387-15066-8.
- Bridges, Douglas; Richman, Fred (1987). Varieties of Constructive Mathematics . Cambridge University Press. ISBN 978-0-521-31802-0.
- Hirst, Jeffry L. (2007). "Representações de reais em matemática reversa" . Boletim da Academia Polonesa de Ciências Matemática . 55 (4): 303–316. doi : 10.4064 / ba55-4-2 .
- Lambov, Branimir (5 de abril de 2015). "RealLib" . GitHub.
- Rice, Henry Gordon (1954). "Números reais recursivos" . Proceedings of the American Mathematical Society . 5 (5): 784–791. doi : 10.1090 / S0002-9939-1954-0063328-5 . JSTOR 2031867 .
- Specker, E. (1949). "Nicht konstruktiv beweisbare Sätze der Analysis" (PDF) . Journal of Symbolic Logic . 14 (3): 145–158. doi : 10.2307 / 2267043 . JSTOR 2267043 .
-
Turing, AM (1936). "Em números computáveis, com uma aplicação ao Entscheidungsproblem". Proceedings of the London Mathematical Society . Series 2 (publicado em 1937). 42 (1): 230–65. doi : 10.1112 / plms / s2-42.1.230 .
Turing, AM (1938). "Em números computáveis, com uma aplicação ao Entscheidungsproblem: uma correção" . Proceedings of the London Mathematical Society . Series 2 (publicado em 1937). 43 (6): 544–6. doi : 10.1112 / plms / s2-43.6.544 .Números computáveis (e as máquinas-a de Turing) foram introduzidos neste artigo; a definição de números computáveis usa sequências decimais infinitas. - Weihrauch, Klaus (2000). Análise computável . Textos em Ciência da Computação Teórica. Springer. ISBN 3-540-66817-9.§1.3.2 introduz a definição por sequências aninhadas de intervalos convergindo para o real singleton. Outras representações são discutidas em §4.1.
- Weihrauch, Klaus (1995). Uma introdução simples à análise computável . Fernuniv., Fachbereich Informatik.
- Stoltenberg-Hansen, V .; Tucker, JV (1999). "Anéis e campos computáveis" . Em Griffor, ER (ed.). Handbook of Computability Theory . Elsevier. pp. 363–448. ISBN 978-0-08-053304-9.
- van der Hoeven, Joris (2006). "Cálculos com números reais efetivos" . Ciência da Computação Teórica . 351 (1): 52–60. doi : 10.1016 / j.tcs.2005.09.060 .