Decidibilidade de números transcendentais

9

Tenho uma pergunta, cuja resposta provavelmente é bem conhecida, mas não consigo encontrar nada significativo depois de algumas pesquisas, por isso gostaria de receber alguma ajuda.

Minha pergunta é se é sabido que decidir se um número é transcendental é indecidível.

Possivelmente, assume-se como entrada, digamos, um programa que retorne o i-ésimo bit do número. Agradecemos antecipadamente por quaisquer ponteiros.

ipsofacto
fonte
5
Se os reais são representados por programas computando um dado bit, ou programas computando aproximações racionais, ou qualquer tipo similar de programa, os únicos conjuntos de reais decidíveis são os triviais (ou seja, aqueles que contêm todos os reais computáveis ​​ou nenhum real computável) , pelo teorema de Rice.
Emil Jerabek
11
Como é mostrada essa implicação?

Respostas:

8

A solução de Kristoffer pode ser usada para mostrar que, supondo que os reais sejam representados, para que possamos calcular limites de sequências de reais que são computáveis ​​Cauchy. Lembre-se de que uma sequência é Cauchy computável se houver um mapa computável f tal que, dado qualquer k que tenhamos | a m - a n | < 2 - k para todos os m , n f ( k(an)nfk|aman|<2km,nf(k). As representações padrão dos reais são assim, por exemplo, onde um real é representado por uma máquina que calcula uma aproximação racional arbitrariamente boa. (Também podemos falar em termos de dígitos de computação, mas temos que permitir dígitos negativos. Esse é um problema bem conhecido na teoria da computabilidade dos reais.)

Teorema: Suponha é um subconjunto de tal modo que existe um calculável sequência ( um n ) n o qual é computably Cauchy e o seu limite de x = lim n um n é fora S . Então a pergunta "é um número real x um elemento de S " é indecidível.SR(an)nx=limnanSxS

Prova. Suponha que fosse decidível. Dada qualquer máquina de Turing T , considere a sequência b n definida como b n = { a n se  T  não tiver parado nos primeiros  n  passos, a m se  T  tiver parado no passo  m  e  m n . É fácil verificar se b n é Cauchy computacionalmente, portanto, podemos calcular seu limite y = lim n b n . Agora temos STbn

bn={anif T has not halted in the first n steps,amif T has halted in step m and mn.
bny=limnbn iff TyST paradas, para que possamos resolver o Deter problema. QED.

Há uma dupla teorema em que assumimos a seqüência está fora , mas seu limite está em S .SS

Exemplos de conjuntos satisfazem essas condições são: um intervalo aberto, um intervalo fechado, os números negativos, o singleton { 0 } , números racionais, números irracionais, números transcendentais, números algébricos etc.S{0}

Um conjunto que não satisfaz as condições do teorema é o conjunto de números racionais traduzidos por um número não computável α . Exercício: S é decidível?S={q+αqQ}αS

Andrej Bauer
fonte
Obrigado pela sua resposta. Apenas um esclarecimento, o teorema diz que, se o conjunto S tem pelo menos um ponto limite fora de S, então decide se um elemento x está em S indecidível? Então, estou um pouco confuso sobre o intervalo fechado nos exemplos.
Ipsofacto 02/03/12
O intervalo fechado segue pela dupla teorema em que você tirar uma sequência fora cujo limite está em S . SS
Andrej Bauer
O que significa para estar "fora de S computávelmente" (em oposição a "fora de S"xSS")?
Isso foi um erro de digitação. Eu espero, obrigado por perceber. Caso contrário, " é computably fora S " pode significar algo como "para cada y S podemos calcular um racional positivo q tal que d ( x , y ) > q ", ou seja, a afirmação " y S . q Q . 0 < q < d ( x , y )xSySqd(x,y)>qyS.qQ.0<q<d(x,y)"é realizado. Mas se você acredita no princípio de Markov, pode reconstruir esse mapa apenas sabendo que não está em S ; portanto, neste caso, não há diferença entre" fora de S e "computacionalmente fora de S ". xSSS
21311 Andrej Bauer #
5

Dado um Turing máquina , definir uma máquina de Turing M ' representa um número do seguinte modo: Na entrada i executar M para i passos na entrada vazio. Se M parou, produza 0 . Caso contrário, imprima o i- bit de π .MMiMiM0iπ

Kristoffer Arnsfelt Hansen
fonte
1

O conjunto de transcendentais não é aberto em (em particular, é denso e codenso em R.) Portanto, é indecidível.RR

David Harris
fonte
4
O conjunto de números reais computáveis ​​não é aberto em (em particular, é denso e codenso em R ), mas é decidível.RR
11
Ricky, isso não é verdade. Dado um oráculo para um número real, você não pode determinar se é computável ou não.
David Harris
11
O conjunto que dei é decidível, pelo algoritmo que sempre responde "Sim". Sua segunda frase mostra que o conjunto que dei não é do tipo dois decidível.
eNe
@Carl: Existe um algoritmo para fornecer um índice eN que é o índice de uma máquina de Turing que calcula um real computável, decida se e é o índice de uma máquina de Turing que calcula um real computável. Esse é o único senso interessante de decidibilidade de conjuntos de reais, porque seu (1) é satisfeito exatamente por conjuntos sem reais computáveis e seu (2) é satisfeito exatamente por {} e R.