É possível testar se um número computável é racional ou inteiro?

18

É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis ​​fornecer as funções isIntegerou isRational?

Suponho que isso não seja possível e que isso esteja de alguma forma relacionado ao fato de que não é possível testar se dois números são iguais, mas não vejo como provar isso.

Edit: Um número computável x é dado por uma função fx(ϵ) que pode retornar uma aproximação racional de x com precisão ϵ : |xfx(ϵ)|ϵ , para qualquer ϵ>0 . Dada essa função, é possível testar se xQ ou ?xZ

dbarbosa
fonte
3
Como é dado o número computável?
Tsuyoshi Ito
10
Como o número é dado é obviamente relevante. Como um exemplo bobo, se a entrada contiver um sinalizador, independentemente de o número ser um número inteiro ou não, decidir se a entrada é um número inteiro ou não é trivial.
Tsuyoshi Ito
3
Pergunta semelhante: cstheory.stackexchange.com/questions/10495/…
Kristoffer Arnsfelt Hansen
3
(1) “Como você sabe que este é um número inteiro?” Por que devo me importar? Você não disse nada sobre requisitos sobre operações. (2) “Se você vê as duas respostas até agora, elas não mencionam nada sobre a implementação.” Não sei o que você quer dizer com “implementação” aqui, ou por que essa frase é relevante para meus comentários.
Tsuyoshi Ito
16
Espero que minha resposta enterre essa discussão. Tsuyoshi, você está enganado, é relevante que operações são computáveis. Não implementamos números reais no vácuo, mas para manipulá-los . De acordo com você, poderíamos usar o tipo de unidade para implementar tudo. Sim, poderíamos, mas algumas operações não seriam computáveis, e esse é precisamente o critério pelo qual julgamos representações.
Andrej Bauer

Respostas:

32

É fácil ficar confuso sobre o que significa "representar" ou "implementar" um número real. De fato, estamos testemunhando uma discussão nos comentários em que a representação é controversa. Então, deixe-me abordar isso primeiro.

Como sabemos que uma implementação está correta?

A teoria que explica como representar as coisas em um computador é realizável . A idéia básica é que, dado um conjunto , escolhemos um tipo de dados τ e para cada x X um conjunto de valores do tipo τ que o realizam . Nós escrevemos v x X quando v é um valor que percebe x . Por exemplo (eu usarei Haskell sem uma boa razão), uma implementação sensata de N pode ser o tipo de dados avaliado para o numeral ¯ k (portanto, em particularXτxXτvxXvxNInteger que quando vvkNvk¯-42 , não representa um número natural e nem um programa divergente). Mas algum palhaço podia andar por e sugerem que usamos Boolpara representar números naturais com e F um l s en N para n 42 . Por que isso está incorreto? Nós precisamos de um critério .True42NFalsenNn42

No caso dos "números coringa", a observação fácil é que a adição não pode ser implementada. Suponha que eu lhe diga que tenho dois números, ambos representados por . Você pode dar um valorizador à soma? Bem, isso depende se a soma é 42, mas você não pode dizer. Como a adição é uma "parte essencial do que são os números naturais", isso é inaceitável. Em outras palavras, a implementação não é sobre conjuntos, mas sobre estruturas , ou seja, temos que representar conjuntos de forma que seja possível implementar também a estrutura relevante. Deixe-me enfatizar isso:False

Implementamos estruturas, não conjuntos vazios. Portanto, precisamos ser capazes de implementar toda a estrutura, juntamente com as operações e todos os axiomas, para que a implementação seja correta.

Se você não respeitar esse princípio, deverá sugerir um critério matemático alternativo de correção. Eu não conheço um.

Exemplo: representação de números naturais

Para números naturais, a estrutura relevante é descrita pelos axiomas de Peano, e o axioma crucial que deve ser implementado é a indução (mas também , sucessor, + e × ). Podemos calcular, usando realizabilidade, o que a implementação da indução faz. Ele acaba sendo um mapa (onde é o tipo de dados ainda desconhecido que representa números naturais)0+×nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

satisfatório induction x f zero = xe induction x f (succ n) = f n (induction x f n). Tudo isso resulta da realização. Temos um critério: uma implementação de números naturais é correta quando permite a implementação de axiomas Peano. Um resultado semelhante seria obtido se usássemos a caracterização de números como a álgebra inicial para o functor .X1+X

Implementação correta de números reais

Vamos voltar a atenção para os números reais e a pergunta em questão. A primeira pergunta a fazer é "qual é a estrutura relevante dos números reais?" A resposta é: o campo ordenado completo de Archimedean Cauchy . Este é o significado estabelecido de "números reais". Você não pode alterá-lo, isso foi corrigido por outros para você (no nosso caso, os reais Dedekind alternativos acabam sendo isomórficos aos reais Cauchy, que estamos considerando aqui.) Você não pode tirar nenhuma parte dele, você não tem permissão para dizer "Eu não ligo para implementar a adição" ou "Eu não ligo para o pedido". Se você fizer isso, não deve chamá-lo de "números reais", mas algo como "números reais, onde esquecemos a ordem linear".

Não vou detalhar todos os detalhes, mas deixe-me explicar como as várias partes da estrutura oferecem várias operações em reais:

  • a axioma arquimediano trata da computação de aproximações racionais de reais
  • a estrutura do campo fornece as operações aritméticas usuais
  • a ordem linear nos fornece um procedimento semidecidável para testar x<y
  • a completude de Cauchy nos dá uma função lim : (nat -> real) -> realque pega uma ( rápida representação) de uma sequência Cauchy e retorna seu limite. (Uma sequência é rápida se | x n - x m |2 min ( n , m ) para todos os m , n(xn)n|xnxm|2min(n,m)m,n .)

O que não obtemos é uma função de teste para a igualdade. Não há nada nos axiomas de reais que pede que ser decidível. (Por outro lado, os axiomas Peano implicam que os números naturais são decidíveis, e você pode provar isso implementando usando apenas como um exercício divertido).=eq : nat -> nat -> Boolinduction

É fato que a representação decimal usual dos reais que a humanidade usa é ruim, porque com ela não podemos sequer implementar adição. O ponto flutuante com mantissa infinita também falha (exercício: por quê?). O que funciona, no entanto, é a representação de dígitos assinados , ou seja, aquela na qual permitimos dígitos negativos e positivos. Ou poderíamos usar sequências de razões que satisfazem o teste rápido de Cauchy, como afirmado acima.

A representação Tsuyoshi também implementa algo, mas não R

Vamos considerar a seguinte representação de reais: um real é representado por um par ( q , b ) onde ( q n ) n é uma sequência rápida de Cauchy convergindo para x e b é um booleano indicando se x é um número inteiro. Para que isso seja uma representação dos reais, teríamos que implementar adição, mas, como se vê, não podemos calcular os sinalizadores booleanos. Portanto, isso não é uma representação dos reais. Mas ainda representa algo, a saber, o subconjunto dos reais Z( RZx(q,b)(qn)nxbxZ(RZ). Na verdade, de acordo com a interpretação que capacidade de realização de uma união é implementado com um sinalizador que indica que parte da união que nos encontramos. A propósito, é um não igual a RZ(RZ)R , a menos que você acreditar em meio excluído, o que não pode ser implementado e, portanto, é bastante irrelevante para esta discussão. Somos forçados pelos computadores a fazer as coisas intuicionisticamente.

Não podemos testar se um real é um número inteiro

Finalmente, deixe-me responder à pergunta que foi feita. Agora sabemos que uma representação aceitável dos reais é uma das rápidas sequências de razões de Cauchy. (Um teorema importante afirma que quaisquer duas representações de reais aceitáveis ​​são na verdade isomórficas).

Teorema: Testar se um real é um número inteiro não é decidível.

Prova. Suponha que possamos testar se um real é um número inteiro (é claro, o real é realizado por uma sequência rápida de Cauchy). A idéia, que permitirá provar um teorema muito mais geral, se você quiser, é construir uma sequência Cauchy rápida de não-números inteiros que converge para um número inteiro. Isso é fácil, basta pegar x n = 2 - n . Em seguida, resolva o problema da parada da seguinte maneira. Dada uma máquina de Turing T , defina uma nova sequência ( y n ) n por y n = { x n se  T(xn)nxn=2nT(yn)n Ou seja, a nova sequência se parece com a sequência(xn)nenquantoTexecutar, mas ficará "presa" emxmseTpára no passom. Muito importante, a nova sequência também é uma sequência rápida de Cauchy (e podemos provar isso sem saber seTpára). Portanto, podemos calcular seu limitez=limnyn

yn={xnif T has not stopped within n stepsxmif T stopped in step m and mn
(xn)nTxmTmTz=limnyn, porque nossa representação de reais está correta. Teste se é um número inteiro. Se for, então deve ser 0 e isso só acontece se T for executado para sempre. Caso contrário, z não é um número inteiro, portanto T deve ter parado. QED.z0TzT

Exercício: adapte a prova acima para mostrar que não podemos testar números racionais. Em seguida, adapte-o para mostrar que não podemos testar algo não trivial (isso é um pouco mais difícil).

Às vezes, as pessoas ficam confusas com todo esse negócio de testes. Eles acham que provamos que nunca podemos testar se um real é um número inteiro. Mas, certamente, 42 é um real e podemos dizer se é um número inteiro. De fato, qualquer real em particular que criamos, , 88 ln 89 , e π sin1188ln89 , etc., podemos perfeitamente dizer se são números inteiros. Precisamente,podemosdizer porquetemosinformações extras: esses reais não nos são dados como sequências, mas como expressões simbólicas das quais podemos calcular o bit Tsuyoshi. Assim que a única informação que temos sobre o real é uma sequência de aproximações racionais convergindo para ele (enãoquero dizer uma expressão simbólica descrevendo a sequência, mas uma caixa preta que gera on-ésimo termo na entradaneπ163nn ), então nós será tão impotente quanto as máquinas.

A moral da história

Não faz sentido falar sobre a implementação de um conjunto, a menos que saibamos que tipo de operações queremos executar nele.

Andrej Bauer
fonte
16
Se minhas respostas fossem esposas, eu só poderia responder uma vez. Ou pelo menos eu teria que excluir a resposta anterior antes de escrever a próxima.
Andrej Bauer
5
@ Max: os primeiros teoremas desse tipo foram dados por Kreisel, Lacombe e Shoenfield (consulte o teorema KLS). Independentemente, Tsteitin deu um teorema que generalizou o KLS e era explicitamente da forma "todo mapa computável é computavelmente contínuo".
Andrej Bauer
6
Eu preciso escrever um livro didático - (Google google google). Ok, bom, você tem mandato. Vá em frente!
21413 Jeff Jeff
10
@ Tsuyoshi: A pergunta usou a frase estabelecida "número real" sem qualificação. A estrutura dos números reais é padrão. Você é livre para considerar outras estruturas, mas não é livre para interpretar mal a terminologia padrão.
Andrej Bauer
21
Tecnicamente falando, você está correto, a palavra "real" não foi usada. Mas você está enganado sobre a definição de números reais. Ou eu diria da seguinte maneira: é uma matemática ruim pensar que os reais são um conjunto particular que vem primeiro, apenas para ser seguido por alguma estrutura. Assim como definimos grupos, anéis, espaços topológicos etc. em termos de sua estrutura, também devemos definir objetos especiais em termos de suas propriedades universais (números naturais são o semirramento inicial, números inteiros o anel inicial, campo inicial dos racionais, reais a .....).
Andrej Bauer
10

Costumo pensar que isso é indecidível:

Seja um número irracional computável. Considere-se uma TM M . Você pode construir uma função que executa M em ϵ e, paralelamente, calcula x com crescente precisão. Se M parar, ele para de calcular x , caso contrário, continua.xMMϵxMx

Decidir se essa função calcula um número racional é equivalente ao problema de parada.

Shaull
fonte
Não entendo sua resposta, você poderia elaborar mais? Não entendo como você o relaciona com o problema de parada e, mais importante, acho que não há razão para parar, mesmo que x seja um número inteiro. Mx
dbarbosa
Como Tsuyoshi apontou, a resposta depende da representação e do modelo de computação. Sua resposta diz corretamente que, se considerarmos que as entradas são números reais computáveis ​​dados por uma TM, então a igualdade não é decidível. Isso está correto, no entanto, não está próximo de nenhum modelo usado na prática.
19413 Kaveh
2
De fato, minha resposta se refere às representações postadas na pergunta, sejam elas práticas ou não. @ dbarbosa - vou explicar: dado um TM , siga a construção na resposta. Então, suponha, por meio de contradição, que você pode decidir se a máquina emitida representa um racional ou não. Se for racional, significa que, em algum momento, M parou e deixamos de calcular o número. Por outro lado, se é irracional, então M não para. Assim, sabemos se M pára, resolvendo o problema da parada, que é conhecido por ser indecidível. MMMM
Shaull
10

Assumindo que um real é dado como uma sequência de aproximações racionais com o erro delimitado por alguma função computável conhecida que tende a zero (todas essas aproximações são equivalentes e correspondem à topologia usual dos reais).

Funções computáveis ​​são contínuas. IsRational e IsInteger não são contínuos e, portanto, não são computáveis.

IsInteger é semi- computável: existe um procedimento que eventualmente produzirá "false" se a entrada não for um número inteiro, mas será executado sempre que a entrada for um número inteiro. Este procedimento simplesmente analisa cada aproximação e verifica se há um número inteiro no limite do erro. Essa função é contínua quando usamos a topologia de Sierpiński em {true, false} (por exemplo, {false} é um conjunto aberto, mas {true} não é).

Máx.
fonte
Obrigado pela resposta. Não entendo o não contínuo => não computável, suponho que você tenha usado um teorema (provavelmente amplamente conhecido) do qual não estou ciente ou que não estou me lembrando. Você poderia fornecer mais detalhes sobre esta etapa?
dbarbosa
1
"computável => contínuo" parece ser um teorema popular - não consigo encontrar uma citação original. A teoria da computação em objetos infinitos e as conexões com a topologia são descritas muito bem (IMO) nesses slides do curso de Brattka ( math.uni.wroc.pl/~pkowa/slides/brattka.pdf ). A proposição 2 dos slides declara que todas as funções computáveis ​​em seqüências de naturais são contínuas; combinado com o teorema 12, obtém-se o resultado para funções de outros tipos.
Max
6

É indecidível se um determinado número computável é igual a zero .

(Portanto, seu oráculo de aproximação racional retorna 0 para cada ε que você tentou? Talvez você não tenha dado um ε suficientemente pequeno.)

Portanto, é indecidível se um determinado número computável entre -½ e + ½ é um número inteiro.

Jeffε
fonte
2

Uma função computável é mais forte do que a função contínua, ou seja, qualquer função computável precisa ser contínua na topologia da informação.

Você quer ver se a função definida porF:R{Yes,No}

F(r)={YESrQNOo.w.

é computável.

rk2nr[k2n,k+12n]n

Então sua função não é contínua e, portanto, não é computável.

M0n[12n,12n]. If M doesn't halt we are done. If it halts, let the largest number that M has asked an approximation for to be m. Then information that M has seen up to this point is consistent with the real number being any real number in the interval [12m,12m], i.e. M doesn't have enough information to correctly solve the problem. If M answers NO then the answer is incorrect. If it answers YES then we can consider running M on any irrational number in the interval [12m,12m] and M will incorrectly answer YES since it will get exactly the same information from the black-box. Therefore M cannot solve the problem correctly.

The proof that any computable function needs to be continuous is similar.

Kaveh
fonte