¿Existe algún algoritmo que pueda existir aunque no sepamos qué es?

En matemáticas, hay muchas pruebas de existencia que no son constructivas, por lo que sabemos que existe cierto objeto, aunque no sabemos cómo encontrarlo.

Estoy buscando resultados similares en informática. En particular: ¿hay algún problema que podamos probar que es decidible sin mostrar un algoritmo para ello? Es decir, sabemos que se puede resolver mediante un algoritmo, pero no sabemos cómo se ve el algoritmo.

El caso más simple que conozco de un algoritmo que existe, aunque no se sabe qué algoritmo, se refiere a autómatas de estado finito.

El cociente de un idioma por un idioma se define como .L $L_1/L_2$$L_1$L 1 / L 2 = { x ∣ ∃ y ∈ L 2  tal que  x y ∈ L 1$L_2$$L_1/L_2=\{x \mid \exists y\in L_2 \text{ such that } xy\in L_1\}$

Se demuestra fácilmente que un conjunto arbitrario cierra el conjunto regular bajo cociente. En otras palabras, si es regular y es arbitrario (no necesariamente regular), entonces es regular.L 2 L 1 / L $L_1$$L_2$$L_1/L_2$

La prueba es bastante simple. Sea una FSA que acepta el conjunto regular , donde y son respectivamente el conjunto de estados y el conjunto de estados de aceptación, y que sea ​​un lenguaje arbitrario. Sea sea ​​el conjunto de estados desde el cual se puede alcanzar un estado final aceptando un cadena a partir de .R Q F L F ′ = { q ∈ Q ∣ ∃ y ∈ $M=(Q,\Sigma,\delta,q_0,F)$$R$$Q$$F$$L$$F'=\{q\in Q\mid \exists y\in L \;\;\delta(q,y)\in F\}$$L$

El autómata , que difiere de sólo en su conjunto de estados finales reconoce precisamente . (O vea Hopcroft-Ullman 1979, página 62 para una prueba de este hecho).M F ′ R /$M'=(Q,\Sigma,\delta,q_0,F')$$M$$F'$$R/L$

Sin embargo, cuando el conjunto no es decidible, puede que no haya un algoritmo para decidir qué estados tienen la propiedad que define . Entonces, aunque sabemos que el conjunto es un subconjunto de , no tenemos un algoritmo para determinar qué subconjunto. En consecuencia, aunque sabemos que es aceptado por una de las posibles FSA, no sabemos cuál es. Aunque debo confesar que sabemos en gran medida cómo se ve.F ′ F ′ Q R 2 | Q $L$$F'$$F'$$Q$$R$$2^{|Q|}$

Este es un ejemplo de lo que a veces se llama una prueba casi constructiva , que es una prueba de que una de un número finito de respuestas es la correcta.

Supongo que una extensión de eso podría ser una prueba de que una de las respuestas enumerables es la correcta. Pero no sé ninguno. Tampoco conozco una prueba puramente no constructiva de que algún problema sea decidible, por ejemplo, usando solo contradicciones.

Para ampliar el comentario original de Hendrick, considere este problema

Dado un número entero ¿hay una corrida de o más 7s consecutivos en la expansión decimal de ?n $n\ge 0$$n$$\pi$

Este problema es decidible, ya que uno de los dos casos puede obtener:

1. Hay un número entero para el cual la expansión decimal de contiene una ejecución de 7 consecutivos, pero ya no se ejecuta.π $N$$\pi$$N$
2. Para cualquier , la expansión de tiene una ejecución de 7s consecutivos.π $n$$\pi$$n$

En el caso (1), un algoritmo de decisión para el problema sería uno de

Si responda "no" más responda "sí".$n > N$

y en el caso (2) el algoritmo sería

Responda "sí".

Claramente cada uno de estos es un algoritmo de decisión; simplemente no sabemos cuál. Sin embargo, eso es suficiente, ya que la capacidad de decisión solo requiere la existencia de un algoritmo, no la especificación de qué algoritmo usar.

Aquí hay una no respuesta. Estoy publicando porque creo que es instructivo, porque originalmente reclamé lo contrario y ocho personas acordaron lo suficiente para votar antes de que @sdcwc señalara el error. No quería editar mi primera respuesta porque no estoy seguro de que muchas personas la hubieran votado si supieran que está equivocada.

$S$$S$

$H$$H$