Décidabilité des nombres transcendantaux

J'ai une question, dont la réponse est probablement bien connue, mais je n'arrive pas à trouver quoi que ce soit de significatif après un peu de recherche, donc j'apprécierais de l'aide.

Ma question est de savoir si l'on sait que décider si un nombre est transcendantal est indécidable.

Eventuellement, on suppose en entrée, disons un programme qui retourne le i ^ ème bit du nombre. Merci d'avance pour tout pointeur.

computability computable-analysis ipsofacto
la source

Si les réels sont représentés par des programmes calculant un bit donné, ou des programmes calculant des approximations rationnelles, ou tout autre type de programme similaire, alors les seuls ensembles décidables de réels sont les triviaux (c'est-à-dire ceux qui contiennent soit tous les réels calculables, soit aucun réel calculable) , par le théorème de Rice.

Emil Jeřábek

Comment cette implication est-elle montrée?

$\:$

Réponses:

La solution de Kristoffer peut être utilisée pour montrer que, en supposant que les réels sont représentés afin que nous puissions calculer les limites des séquences de réels qui sont calculables Cauchy. Rappelons qu'une séquence est calculable de Cauchy s'il existe une carte calculable telle que, étant donné tout nous avons pour tout $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(k)$ . Les représentations standard des réels sont comme ça, par exemple celle où un réel est représenté par une machine qui calcule une approximation rationnelle arbitrairement bonne. (Nous pouvons également parler de calcul des chiffres, mais nous devons ensuite autoriser les chiffres négatifs. C'est un problème bien connu dans la théorie de la calculabilité des réels.)

$S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Preuve. Supposons que soit décidable. Étant donné n'importe quelle machine de Turing , considérons la séquence définie comme Il est facile de vérifier que est calculable Cauchy, donc nous pouvons calculer sa limite . Maintenant, nous avons iff s'arrête, donc nous pouvons résoudre le problème d'arrêt. QED. $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$

y \in S

$y \in S$

T

$T$

Il y a un théorème double dans lequel nous supposons que la séquence est en dehors , mais sa limite est en . $S$ $S$

Des exemples d'ensembles satisfaisant à ces conditions sont: un intervalle ouvert, un intervalle fermé, les nombres négatifs, le singleton , les nombres rationnels, les nombres irrationnels, les nombres transcedentaux, les nombres algébriques, etc. $S$ $\lbrace 0 \rbrace$

Un ensemble qui ne satisfait pas aux conditions du théorème est l'ensemble des nombres rationnels traduits par un non calculable nombre . Exercice: est-il décidable? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $S$

Andrej Bauer
la source

Merci pour votre réponse. Juste une clarification, le théorème dit-il que si l'ensemble S a au moins un point limite en dehors de S, alors décider si un élément x est dans S indécidable? Ensuite, je suis un peu confus au sujet de l'intervalle fermé dans les exemples.

ipsofacto

L'intervalle fermé suit par le théorème dual dans lequel on prend une séquence en dehors de dont la limite est dans .

S

$S$

S

$S$

Andrej Bauer

Que signifie que soit "hors calculable" (par opposition à "hors ") :?

x

$x$

S

$S$

S

$S\hspace{.01 in}$

$\:$

$\;\;$

C'était une faute de frappe. Je le fidex, merci de l'avoir remarqué. Sinon, " est calculable en dehors de " pourrait signifier quelque chose comme "pour chaque nous pouvons calculer un rationnel positif tel que ", c'est-à-dire la déclaration " "est réalisé. Mais si vous croyez au principe de Markov, alors vous pouvez reconstruire une telle carte en sachant simplement que n'est pas dans , donc dans ce cas il n'y a pas de différence entre «en dehors de et« en dehors de calculable ».

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)$

x

$x$

S

$S$

S

$S$

S

$S$

Andrej Bauer

Étant donné une machine de Turing , définissez une machine de Turing représentant un nombre comme suit: Sur l'entrée lance pendant étapes sur l'entrée vide. Si s'est arrêté, affichez . Sinon, sortez le ème bit de . $M$ $M'$ $i$ $M$ $i$ $M$ $0$ $i$ $\pi$

Kristoffer Arnsfelt Hansen
la source

L'ensemble des transcendantaux n'est pas ouvert dans (en particulier, il est dense et codense dans Il est donc indécidable. $\mathbf R$ $\mathbf R$

David Harris
la source

L'ensemble des nombres réels calculables n'est pas ouvert dans (en particulier, il est dense et codense dans ), mais il est décidable.

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

Ricky, ce n'est pas vrai. Étant donné un oracle pour un nombre réel, vous ne pouvez pas déterminer s'il est calculable ou non.

David Harris

L'ensemble que j'ai donné est décidable, par l'algorithme qui répond toujours "Oui". Votre deuxième phrase montre que l'ensemble que j'ai donné n'est pas décidable de type deux.

$\:$

$\;\;$

@Ricky Demer: L'ensemble des nombres réels calculables est indécidable dans deux sens: (1) étant donné un index arbitraire , décidez si est l'indice d'une machine de Turing qui calcule un réel calculable. (2) étant donné une séquence de Cauchy arbitraire à convergence rapide, déterminer s'il s'agit d'une séquence calculable. Il n'y a pas de bon sens dans lequel l'ensemble des nombres réels calculables est décidable.

e \in N

$e \in \mathbb{N}$

e

$e$

Carl Mummert

@Carl: Il existe un algorithme pour donner un index qui est l'index d'une machine de Turing qui calcule un réel calculable, décidez si est l'index d'une machine de Turing qui calcule un réel calculable. C'est le seul sens intéressant de décidabilité des ensembles de réels, car votre (1) est satisfait exactement par des ensembles sans réels calculables et votre (2) est satisfait exactement par et .

e \in N

$\: e\in \mathbb{N} \:$

e

$e$

$\hspace{.1 in}$

$\;\;$

$\hspace{.2 in}$

$\hspace{2.2 in}$

{}

$\: \{\} \:$

R

$\mathbf{R}$

$\;\;\;$