Propiedades definibles de reales computables

Sí, el teorema de Rice para los reales se mantiene en todas las versiones razonables de los reales computables.

Primero probaré un cierto teorema y un corolario, y luego explicaré qué tiene que ver con la computabilidad.

Teorema: Suponga que es un mapa y dos reales tales que y . Entonces existe una secuencia de Cauchy tal que para todo $p : \mathbb{R} \to \{0,1\}$ $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}$

Prueba. Construimos una secuencia de pares de reales siguiente manera: $(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*}$ Observe que para todos los

i \in N

$i \in \mathbb{N}$

y $p(y_i) = 0$ $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}$

Por lo tanto, las secuencias y son Cauchy y convergen en un punto común . Si entonces tomamos , y si tomamos $(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$

Corolario: Suponga que y dos reales tales que y . Entonces, cada máquina de Turing funciona para siempre o no funciona para siempre. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$

Prueba. Por el teorema, hay una secuencia de Cauchy tal que para todos . Sin pérdida de generalidad, podemos suponer que y . $(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$

Deje que sea una máquina de Turing. Defina una secuencia por La secuencia está bien definida porque podemos simular hasta pasos y decidir si se ha detenido o no dentro de tantos pasos. Luego, observe que es una secuencia de Cauchy porque $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$

es una secuencia de Cauchy (dejamos esto como un ejercicio). Deje

. O

(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 entonces ejecuta para siempre. De hecho, si se detuvo después de pasos, entonces tendríamos , y entonces contradeciría . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
si entonces no se ejecuta para siempre. De hecho, si lo hiciera, entonces tendríamos , y entonces , contradiciendo . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Ahora podemos explicar por qué esto nos da el teorema de Rice para números reales. Las pruebas son constructivas, por lo tanto, producen procedimientos computables. Esto es cierto para cualquier modelo de computabilidad y cualquier estructura de cómputo de reales que merezcan ser llamados así. De hecho, puede regresar y leer la prueba como instrucciones para construir un programa: todos los pasos son computables.

Por lo tanto, si tuviéramos un mapa computable y computable tal que y , entonces podríamos aplicar los procedimientos computables que surgen de pruebas constructivas del teorema y el corolario para crear el oráculo de detención. Pero el oráculo de detención no existe, por lo tanto, cada mapa computable $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$ es constante

Suplementario: también hubo una pregunta sobre si el teorema de Rice está relacionado con la conexión de los reales. Sí, es esencialmente la afirmación de que los reales están conectados.

Primero observemos que un mapa continuo (tomamos la topología discreta en ) corresponde a un par de clopen disjuntos (cerrados y abiertos) establece tal que . De hecho, tome y $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ . Debido a que es continua y y están abiertos, y estarán abiertas, disjuntos, y obviamente cubren todos . Por el contrario, cualquier par de clopens disjuntos que cubran determina un mapa continuo que asigna elementos de a y elementos de a . $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ $U$ $0$ $V$ $1$

De esto aprendemos que un espacio se desconecta si, y solo si, existe un mapa continuo y tal que y (necesitamos y para que podamos obtener una descomposición no trivial de ). Hay otra forma de decir lo mismo: un espacio está conectado si, y solo si, todos los mapas continuos $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ son constantes. $X \to \{0,1\}$

En matemática computable tenemos un teorema básico: cada mapa computable es continuo . Entonces, siempre y cuando estemos dentro del ámbito de los objetos computables, el teorema de Rice afirma que cierto espacio está conectado. En el caso del teorema clásico del arroz del espacio en cuestión es el espacio de las funciones computables parciales . $\mathbb{N} \to \mathbb{N}$

Andrej Bauer
fuente

¡Gracias! Esto es lo que estaba buscando. ¿Alguna idea sobre la otra pregunta: si esto está directamente relacionado con la conexión de los reales?

Shachaf

Agregué una explicación sobre el hecho de que el teorema de Rice es de hecho una forma de teorema de conectividad.

Andrej Bauer

Suponga que

y defina

no se detiene dentro de

pasos e

contrario. Si T no detiene a continuación

converge a

, si no converge a

. Si

son computables, entonces dado

, se puede generar una máquina que calcule el límite de

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$

. ¿Por qué esto no es suficiente para mostrar que

no puede ser computable, o incluso semidecidable (ya que

no se detiene si f

en el límite)? Obviamente me falta algo, ya que hay propiedades no triviales que son semidecidibles.

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$

Ariel el

Su definición de

está bien, pero también necesita una tasa computable de convergencia de la sucesión

con el fin de afirmar que su límite es computable. Puesto que no podemos calcular en el que el índice

de la secuencia

podría saltar de

(o de lo que podríamos calcular en qué etapa

se detendrá), una velocidad tal computable de convergencia no puede ser tenía.

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

Andrej Bauer el

No. O, al menos, la prueba no es trivial, ya que puede elegir entre las (generalmente muchas) formas posibles de calcular un real, y puede elegir una con una estructura que sea total wrt la propiedad elegida para que no reduce la prueba de la propiedad al problema de detención.

Además, creo que necesito una mejor comprensión de lo que "no trivial" significa wrt las propiedades de los números. Para el teorema de Rice, "no trivial" es básicamente no sintáctico y no está implícito en la sintaxis. Sin embargo, cada número real computable no es un solo programa, sino una clase de equivalencia llena de programas.

Boyd Stephen Smith Jr.
fuente

I'm not sure what you mean, here. Are you trying to distinguish between computable real numbers (e.g.,

2

$2$ ,

22 / 7

$22/7$ ,

π

$\pi$ , etc.) and the programs that compute them? Sure, there are infinitely many programs that compute each computable real but there are also infinitely many Turing machines that decide any decidable language, and the ordinary Rice's theorem doesn't have any problem with that.

David Richerby

¿Las diferentes representaciones de reales computables tienen propiedades de computabilidad significativamente diferentes? Digamos que estoy usando una de las definiciones en en.wikipedia.org/wiki/Computable_number , por ejemplo, un programa real que se representa mediante un programa que toma un límite de error racional y produce una aproximación dentro de ese límite. Me refiero a "trivial" en el mismo sentido que el teorema de Rice: una propiedad que se aplica a todos los reales computables o a ninguno de ellos. Es cierto que cada número puede ser representado por múltiples programas, pero eso también es cierto para las funciones parciales.

Shachaf

@ Shachaf Eso es más "trivial" de lo que requiere el Teorema de Rice. Las propiedades "sintácticas" también son triviales, por ejemplo, "tiene al menos 4 estados accesibles desde el estado inicial", "tiene un gráfico de estado conectado", "no tiene transición que escriba X en la cinta", etc., y necesitan No se aplica a todas las máquinas.

Boyd Stephen Smith Jr.

@DavidRicherby Yes, I think the distinction is necessary. If you are able to work exclusively with total or productive representations, you have more power.

Boyd Stephen Smith Jr.

El teorema de Rice se trata de propiedades de funciones parciales, no de algoritmos que las computan. De manera similar, estoy preguntando sobre las propiedades de los reales computables, no sobre los programas que las computan.

Shachaf

Propiedades definibles de reales computables

Respuestas: