Propriétés décidables des réels calculables

Oui, le théorème de Rice pour les réels est valable dans toutes les versions raisonnables des réels calculables.

Je vais d'abord prouver un certain théorème et un corollaire, et expliquer plus tard ce que cela a à voir avec la calculabilité.

Théorème: Supposons que $p : \mathbb{R} \to \{0,1\}$ est une carte et deux réels tels que et . Il existe alors une séquence de Cauchy telle que pour tout . $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$ $(x_i)_i$ $p(\lim_i x_i) \neq p(x_j)$ $j \in \mathbb{N}$

Preuve. Nous construisons une séquence de paires de réels comme suit: Observez cela pour tout : $(y_i, z_i)_i$

\begin{aligned} (y_{0}, z_{0}) & = (a, b) \\ (y_{i + 1}, z_{i + 1}) & = {\begin{cases} (y_{i}, (y_{i} + z_{i}) / 2) & if p ((y_{i} + z_{i}) / 2) = 1 \\ ((y_{i} + z_{i}) / 2, z_{i}) & if p ((y_{i} + z_{i}) / 2) = 0 \end{cases} \end{aligned}

$\begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*}$

i \in N

$i \in \mathbb{N}$

$p(y_i) = 0$ et $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Ainsi les séquences et sont Cauchy et elles convergent vers un point commun . Si alors nous prenons , et si alors nous prenons . $(y_i)_i$ $(z_i)_i$ $c = \lim_i y_i = \lim_i z_i$ $p(c) = 0$ $(x_i)_i = (z_i)_i$ $p(c) = 1$ $(x_i)_i = (y_i)_i$ $\square$

Corollaire: Supposons et deux réels tels que et . Ensuite, chaque machine Turing fonctionne pour toujours ou ne fonctionne pas pour toujours. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$

Preuve. Par le théorème, il existe une séquence de Cauchy telle que pour tout . Sans perte de généralité, nous pouvons supposer que et . $(x_i)_i$ $p(x_j) \neq p(\lim_i x_i)$ $j \in \mathbb{B}$ $p(x_j) = 1$ $p(\lim_i x_i) = 0$

Soit une machine de Turing. Définissez une séquence par La séquence est bien définie car nous pouvons simuler jusqu'à étapes et décider si elle s'est arrêtée ou non dans ce nombre d'étapes. Ensuite, observez que est une séquence de Cauchy car est une séquence de Cauchy (nous laissons cela comme un exercice). Soit . Soit ou : $T$ $y_i$

y_{i} = {\begin{cases} x_{j} & if T halts in step j and j \leq i \\ x_{i} & if T does not halt within i steps \end{cases}

$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases}$

T

$T$

i

$i$

(y_{i})_{i}

$(y_i)_i$

(x_{i})_{i}

$(x_i)_i$

z = lim_{i} y_{i}

$z = \lim_i y_i$

p (z) = 0

$p(z) = 0$

p (z) = 1

$p(z) = 1$

si alors s'exécute pour toujours. En effet, s'il s'arrêtait après étapes, alors nous aurions , et donc contredirait . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
si alors ne s'exécute pas indéfiniment. En effet, si c'était le cas, alors nous aurions , et donc , contredisant . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Nous pouvons maintenant expliquer pourquoi cela nous donne le théorème de Rice pour les nombres réels. Les preuves sont constructives, donc elles donnent des procédures calculables. Cela est vrai de tout modèle de calculabilité et de toute structure de calcul de réels qui méritent d'être appelés ainsi. En fait, vous pouvez revenir en arrière et lire la preuve comme des instructions pour la construction d'un programme - toutes les étapes sont calculables.

Ainsi, si nous avions une carte calculable et calculable telle que et , alors nous pourrions appliquer les procédures calculables découlant des preuves constructives du théorème et du corollaire pour créer l'oracle de Halting. Mais l'oracle Halting n'existe pas, par conséquent, chaque carte calculable est constante. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$

Supplémentaire: Il y avait aussi une question de savoir si le théorème de Rice était lié à la connectivité des réels. Oui, c'est essentiellement la déclaration que les réels sont connectés.

Observons d'abord qu'une carte continue (on prend la topologie discrète sur ) correspond à une paire d'ensembles clopen disjoints (fermés et ouverts) tel que . En effet, prenons et . Parce que est continue et et sont ouverts, et seront ouverts, disjoints, et ils couvrent évidemment tous . Inversement, toute paire de clopens disjoints qui couvrent détermine une carte continue $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ qui mappe les éléments de à et les éléments de à . $U$ $0$ $V$ $1$

De cela, nous apprenons qu'un espace est déconnecté si, et seulement si, il existe une carte continue et telle que et (nous avons besoin de et pour obtenir une décomposition non triviale de ). Il y a une autre façon de dire la même chose: un espace est connecté si, et seulement si, toutes les cartes continues sont constantes. $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ $X \to \{0,1\}$

En mathématiques calculables, nous avons un théorème de base: chaque carte calculable est continue . Donc, tant que nous sommes dans le domaine des objets calculables, le théorème de Rice déclare en fait qu'un certain espace est connecté. Dans le cas du théorème classique de Rice, l'espace en question est l'espace des fonctions calculables partielles . $\mathbb{N} \to \mathbb{N}$

Andrej Bauer
la source

Merci! C'est ce que je cherchais. Une idée de l'autre question - si cela est directement lié à la connectivité des réels?

Shachaf

J'ai ajouté une explication sur le fait que le théorème de Rice est en fait une forme de théorème de connectivité.

Andrej Bauer

Supposons que et définissez si ne s'arrête pas en étapes et sinon. Si T ne s'arrête pas alors converge vers , sinon il converge vers . Si sont calculables, alors étant donné , on peut générer une machine calculant la limite de . Pourquoi cela ne suffit-il pas pour montrer que ne peut être ni calculable, ni même semi-décidable (car n'arrête pas ssi est

p (x) = 1, p (x^{'}) = 0

$p(x)=1, p(x')=0$

y_{i} = x

$y_i=x$

T

$T$

i

$i$

y_{i} = x^{'}

$y_i=x'$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

x, x^{'}

$x,x'$

T

$T$

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$ sur la limite). De toute évidence, il me manque quelque chose, car il existe des propriétés non triviales qui sont semi-décidables.

Ariel

Votre définition de est correcte, mais vous avez également besoin d'un taux de convergence calculable de la séquence afin de prétendre que sa limite est calculable. Puisque nous ne pouvons pas calculer à quel indice la séquence pourrait passer de à (ou bien nous pourrions calculer à quelle étape s'arrêtera), un tel taux de convergence calculable ne peut pas être obtenu.

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

Andrej Bauer

Non. Ou, au moins, la preuve n'est pas anodine, car vous pouvez choisir parmi les (généralement plusieurs) façons possibles de calculer un réel, et vous pouvez en choisir une avec une structure qui est totale par rapport à la propriété choisie afin que vous ne réduisez pas le test de la propriété au problème d'arrêt.

De plus, je pense que j'ai besoin de mieux comprendre ce que signifie "non trivial" par rapport aux propriétés des nombres. Pour le théorème de Rice, «non trivial» est fondamentalement non syntaxique et n'est pas impliqué par la syntaxe. Cependant, chaque nombre réel calculable n'est pas un programme unique, mais plutôt une classe d'équivalence pleine de programmes.

Boyd Stephen Smith Jr.
la source

Je ne sais pas ce que tu veux dire ici. Essayez-vous de faire la distinction entre des nombres réels calculables (par exemple, , , , etc.) et les programmes qui les calculent? Bien sûr, il existe une infinité de programmes qui calculent chaque réel calculable, mais il existe également une infinité de machines Turing qui décident de tout langage décidable, et le théorème de Rice ordinaire n'a aucun problème avec cela.

2

$2$

22 / 7

$22/7$

π

$\pi$

David Richerby

Les différentes représentations de réels calculables ont-elles réellement des propriétés de calcul significativement différentes? Supposons que j'utilise l'une des définitions de en.wikipedia.org/wiki/Computable_number , par exemple, un réel calculable est représenté par un programme qui prend une limite d'erreur rationnelle et produit une approximation dans cette limite. Je veux dire "trivial" dans le même sens que le théorème de Rice: une propriété qui s'applique à tous les réels calculables ou à aucun d'entre eux. Il est vrai que chaque nombre peut être représenté par plusieurs programmes, mais cela vaut également pour les fonctions partielles.

Shachaf

@Shachaf C'est plus "trivial" que ne l'exige le théorème de Rice. Les propriétés "syntaxiques" sont également triviales - par exemple "a au moins 4 états accessibles depuis l'état initial", "a un graphe d'état connecté", "n'a pas de transition qui écrit X sur la bande", etc. - et ils ont besoin ne s'applique pas à chaque machine.

Boyd Stephen Smith Jr.

@DavidRicherby Oui, je pense que la distinction est nécessaire. Si vous êtes capable de travailler exclusivement avec des représentations totales ou productives, vous avez plus de pouvoir.

Boyd Stephen Smith Jr.

Le théorème de Rice concerne les propriétés des fonctions partielles, pas les algorithmes qui les calculent. De même, je pose des questions sur les propriétés des réels calculables, pas sur les programmes qui les calculent.

Shachaf

Propriétés décidables des réels calculables

Réponses: