¿Pruebas no constructivas de decidibilidad?

Question

¿Existen ejemplos de conjuntos de números naturales que se ha demostrado que son decidibles pero solo mediante pruebas no constructivas?

Answer 1

Cuando enseño computabilidad, suelo usar el siguiente ejemplo para ilustrar el punto.

Sea $f(n)=1$, si hay $n$ unos consecutivos en algún lugar de la expansión decimal de $\pi$, y $f(n)=0$ en caso contrario. ¿Es esta una función computable?

Algunos estudiantes podrían intentar calcularlo de manera ingenua de la siguiente manera: dado un valor $n$, comenzar a enumerar los dígitos de $\pi$, y buscar $n$ unos consecutivos. Si se encuentra, entonces se genera una salida de $1$. Pero luego se dan cuenta: ¿qué pasa si en una entrada en particular, han buscado durante 10 años y aún no han encontrado la instancia? No parecería justificado generar una salida de $0", ya que quizás podrían encontrar los unos consecutivos buscando un poco más.

Sin embargo, podemos probar que la función es computable de la siguiente manera. O bien hay cadenas arbitrariamente largas de unos en $\pi$ o hay una cadena más larga de unos de longitud $N$. En el primer caso, la función $f$ es la función constante $1$, que definitivamente es computable. En el segundo caso, $f$ es la función con valor de $1$ para todas las entradas $n\lt N$ y valor de $0$ para $n\geq N$, lo cual para cualquier $N$ fijo también es una función computable.

Por lo tanto, hemos demostrado que $f$ es computable en efecto proporcionando una lista infinita de programas y demostrando que uno de ellos calcula $f$, pero no sabemos exactamente cuál. De hecho, creo que es una pregunta abierta de teoría de números cuál de los casos es el correcto. En este sentido, este ejemplo tiene cierta similitud con los ejemplos de Gerhard.

Answer 2

El teorema de Robertson-Seymour implica que toda familia cerrada por subgráficos $F$ de gráficos finitos es decidible en tiempo $O(n^3)$. Sin embargo, no proporciona un algoritmo explícito hasta que se suministra una lista finita explícita de subgráficos prohibidos que caracterizan a $F; la prueba de que dicha lista siempre existe es no constructiva.

Answer 3

Hay el ejemplo estándar que involucra el Último Teorema de Fermat, excepto que ahora tenemos una buena idea de cuál es el conjunto. Por lo tanto, vamos a reemplazarlo por "el entero positivo más pequeño n que es un múltiplo de 4 y para el cual no existe ninguna matriz de Hadamard de orden n, o 1 si existen matrices de Hadamard de todos los órdenes posibles". Esto define un conjunto unitario, que es decidible. Podrías argumentar que en principio es constructivo, mientras que yo argumentaría que dado que todavía no conocemos los determinantes maximales para órdenes pequeños menores de 100, tú y tus presuntos bisnietos no verán un valor para n, por lo que tendrás dificultades para demostrarme que existe una construcción basada en esta definición, ya que no hay garantía de terminación de la construcción.

Alternativamente, cualquier conjunto finito que se haya obtenido mediante medios no constructivos (por ejemplo, codificaciones de contraejemplos a la conjetura de las familias unión-cerradas de Frankl, donde se presume que la demostración de que solo hay finitos es no constructiva) debería contar como un ejemplo.

Las respuestas mejores surgirán una vez que se haya especificado una buena noción de no constructivo. En cuanto a tal noción, dejaré las discusiones filosóficas a otros.

Gerhard "Pregúntame sobre Diseño de Sistemas" Paseman, 10.02.2010

Answer 4

Suponga que su conjunto $A\subseteq\mathbb{N}$ es decidible, es decir, $\forall_n (n\in A\vee n\not\in A)$. El Principio de Markov asegura que su conjunto es computable. Como es computable, puede ser descrito por una $\Pi_2^0$-Fórmula, y esto es demostrable en la Aritmética de Peano. Por lo tanto, utilizando la Traducción de Friedman, encontrará una prueba constructiva de su decidibilidad a partir de la Aritmética de Heyting.

Eso es todo para los conjuntos con decidibilidad demostrable a partir de la Aritmética de Peano. Por supuesto, existen cosas como el Teorema de Goodstein, en los que este teorema podría no ser aplicable. En este caso, debe especificar qué sistema constructivo más fuerte desea. Pero probablemente, también se apliquen teoremas similares en ese caso.

Answer 5

De hecho, existen algunos teoremas matemáticos con pruebas no constructivas que no pueden tener ninguna prueba constructiva (ahora o nunca). Aquí hay un ejemplo:

Definición. Sea $\boldsymbol\varphi_1,\boldsymbol\varphi_2,\boldsymbol\varphi_3,\cdots$ una lista de todas las funciones computables parciales unarias (de $\mathbb{N}$ a $\mathbb{N}$). Denotar la Complejidad de Chaitin-Kolmogorov por $\mathcal{C}$ que se define por $\mathcal{C}(n)=\min \{e\mid\boldsymbol\varphi_e(0)\!\downarrow = n\}$.

Nótese que $\mathcal{C}$ es una función total ($\mathcal{C}:\mathbb{N}\rightarrow\mathbb{N}$).

El siguiente teorema tiene una prueba no constructiva:

Teorema 1. Para cada número natural $n$ existe algún $m$ tal que $\mathcal{C}(m)\!>\!n$. Es decir, $\forall y \exists x \mathcal{C}(x)\!>\!y$.

Prueba: Para cada $i\leqslant n$ ponga $\alpha_i=\boldsymbol\varphi_i(0)$ si el valor existe, es decir, $\boldsymbol\varphi_i(0)\!\downarrow$; de lo contrario, deje $\alpha_i=0$. Tome $m$ como cualquier número natural mayor que todos los $\alpha_i$. $\texttt{QED}$

De hecho, el teorema anterior no puede tener ninguna demostración constructiva:

Teorema 2. No existe una función computable $f$ tal que para cada número natural $n$ se tenga $\mathcal{C}\big(f(n)\big)\!>\!n$.

Prueba: Si hubiera tal función computable (y total), entonces por el Teorema de Recursión de Kleene (también conocido como Teorema del Punto Fijo) existiría algún $\mathbf{e}$ tal que $\boldsymbol\varphi_{\mathbf{e}}(0)=f(\mathbf{e})$. Para este $\mathbf{e}$ entonces tendríamos $\mathcal{C}\big(f(\mathbf{e})\big)\leqslant\mathbf{e}$ contradiciendo la suposición de $\forall n: \mathcal{C}\big(f(n)\big)\!>\!n$. $\texttt{QED}$

Ahora, tenemos un ejemplo de un conjunto decidable cuya decidibilidad no puede ser probada de manera constructiva:

Sea $\mathfrak{B}=\{n\in\mathbb{N}\mid \exists m: \mathcal{C}(m)>n\}$. Sabemos que $\mathfrak{B}$ es decidable simplemente porque $\mathfrak{B}=\mathbb{N}$. Pero si alguien (ahora o en el futuro) puede tener alguna prueba constructiva de su decidibilidad, debería poder calcular la función característica $\chi_{\mathfrak{B}}$ de $\mathfrak{B}$ (definida por $\chi_{\mathfrak{B}}(x)=0$ si $x\not\in\mathfrak{B}$ y $\chi_{\mathfrak{B}}(x)=1$ si $x\in\mathfrak{B}$). Eso equivaldría a mostrar que $\chi_{\mathfrak{B}}=\mathbf{1}$ la función constante $1$. Por lo tanto, cualquier prueba constructiva de la decidibilidad de $\mathfrak{B}$ mostraría (constructivamente) que $\mathfrak{B}=\mathbb{N}$ y así proporcionaría una función computable $f$ tal que $\forall n\!\in\!\mathbb{N}: \mathcal{C}\big(f(n)\big)\!>\!n$; contradiciendo el Teorema 2.

Por lo tanto, creo que $\mathfrak{B}$ es un conjunto decidable tal que ninguna prueba de su decidibilidad puede ser constructiva.