É 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 isInteger
ou 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 é dado por uma função que pode retornar uma aproximação racional de com precisão : , para qualquer . Dada essa função, é possível testar se ou ?
computability
computing-over-reals
lambda-calculus
graph-theory
co.combinatorics
cc.complexity-theory
reference-request
graph-theory
proofs
np-complete
cc.complexity-theory
machine-learning
boolean-functions
combinatory-logic
boolean-formulas
reference-request
approximation-algorithms
optimization
cc.complexity-theory
co.combinatorics
permutations
cc.complexity-theory
cc.complexity-theory
ai.artificial-intel
p-vs-np
relativization
co.combinatorics
permutations
ds.algorithms
algebra
automata-theory
dfa
lo.logic
temporal-logic
linear-temporal-logic
circuit-complexity
lower-bounds
permanent
arithmetic-circuits
determinant
dc.parallel-comp
asymptotics
ds.algorithms
graph-theory
planar-graphs
physics
max-flow
max-flow-min-cut
fl.formal-languages
automata-theory
finite-model-theory
dfa
language-design
soft-question
machine-learning
linear-algebra
db.databases
arithmetic-circuits
ds.algorithms
machine-learning
ds.data-structures
tree
soft-question
security
project-topic
approximation-algorithms
linear-programming
primal-dual
reference-request
graph-theory
graph-algorithms
cr.crypto-security
quantum-computing
gr.group-theory
graph-theory
time-complexity
lower-bounds
matrices
sorting
asymptotics
approximation-algorithms
linear-algebra
matrices
max-cut
graph-theory
graph-algorithms
time-complexity
circuit-complexity
regular-language
graph-algorithms
approximation-algorithms
set-cover
clique
graph-theory
graph-algorithms
approximation-algorithms
clustering
partition-problem
time-complexity
turing-machines
term-rewriting-systems
cc.complexity-theory
time-complexity
nondeterminism
dbarbosa
fonte
fonte
Respostas:
É 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 τ x ∈ X τ v ⊢ x ∈ X v x N v ⊢ k ∈ N v k¯¯¯ True⊢42∈N False⊢n∈N n≠42
Integer
que quando v-42
, não representa um número natural e nem um programa divergente). Mas algum palhaço podia andar por e sugerem que usamosBool
para representar números naturais com e F um l s e ⊢ n ∈ N para n ≠ 42 . Por que isso está incorreto? Nós precisamos de um critério .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
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
satisfatórioX↦1+X
induction x f zero = x
einduction 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 .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:
lim : (nat -> real) -> real
que 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 , nO 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 -> Bool
induction
É 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ãoR
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 ∪ ( R ∖ Zx (q,b) (qn)n x b x Z∪(R∖Z) . 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∪(R∖Z) 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)n xn=2−n T (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
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 π √sin11 88ln89 , 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π163√ n n ), 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.
fonte
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.x M M ϵ x M x
Decidir se essa função calcula um número racional é equivalente ao problema de parada.
fonte
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 é).
fonte
É 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.
fonte
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}
é computável.
Então sua função não é contínua e, portanto, não é computável.
The proof that any computable function needs to be continuous is similar.
fonte