Decidibilidade de números transcendentais

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.

computability computable-analysis ipsofacto
fonte

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

Como é mostrada essa implicação?

$\:$

Respostas:

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 tal que, dado qualquer que tenhamos para todos os $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(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 o qual é computably Cauchy e o seu limite de é fora . Então a pergunta "é um número real um elemento de " é indecidível. $S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Prova. Suponha que fosse decidível. Dada qualquer máquina de Turing , considere a sequência definida como É fácil verificar se é Cauchy computacionalmente, portanto, podemos calcular seu limite . Agora temos $S$ $T$ $b_n$

b_{n} = {\begin{cases} a_{n} & if T has not halted in the first n steps, \\ a_{m} & if T has halted in step m and m \leq n . \end{cases}

$b_n = \begin{cases} a_n & \text{if $T$ has not halted in the first $n$ steps,}\\ a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.} \end{cases}$

b_{n}

$b_n$

y = lim_{n} b_{n}

$y = \lim_n b_n$

iff

y \in S

$y \in S$

T

$T$ 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$ $S$

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

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: é decidível? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $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

$S$

S

$S$

Andrej Bauer

O que significa para

estar "fora de

computávelmente" (em oposição a "fora de

x

$x$

S

$S$

S

$S\hspace{.01 in}$ ")

$\:$ ?

$\;\;$

Isso foi um erro de digitação. Eu espero, obrigado por perceber. Caso contrário, "

é computably fora

" pode significar algo como "para cada

podemos calcular um racional positivo

tal que

", ou seja, a afirmação "

x

$x$

S

$S$

y \in S

$y \in S$

q

$q$

d (x, y) > q

$d(x,y) > q$

\forall y \in S . \exists q \in Q . 0 < q < d (x, y)

$\forall y \in S . \exists q \in \mathbb{Q} . 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

; portanto, neste caso, não há diferença entre" fora de

e "computacionalmente fora de

x

$x$

S

$S$

S

$S$

S

$S$

21311 Andrej Bauer #

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

Kristoffer Arnsfelt Hansen
fonte

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

David Harris
fonte

O conjunto de números reais computáveis não é aberto em

(em particular, é denso e codenso em

), mas é decidível.

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

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

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.

$\;\;$

e \in N

$e \in \mathbb{N}$

e

$e$

@Carl: Existe um algoritmo para fornecer um índice

e \in N

$\: e\in \mathbb{N} \:$ que é o índice de uma máquina de Turing que calcula um real computável, decida se

e

$e$ é o índice de uma máquina de Turing que calcula

$\hspace{.1 in}$ um real computável.

$\;\;$ Esse é o único senso interessante de decidibilidade de conjuntos de reais, porque

$\hspace{.2 in}$ seu (1) é satisfeito exatamente por conjuntos sem reais computáveis

$\hspace{2.2 in}$ e seu (2) é satisfeito exatamente por

{}

$\: \{\} \:$ e

R

$\mathbf{R}$ .

$\;\;\;$