¿Por qué los humanos pueden resolver ciertos problemas "indecidibles"?

La coincidencia de patrones de alto orden es un problema indecidible. Eso significa que no existe un algoritmo que, dada una ecuación a => b, donde ay bson términos abiertos en el cálculo lambda simplemente tipeado, encuentre una sustitución Stal que aS => bS, donde =>significa "tiene la misma forma normal de Bn". Sin embargo, los humanos pueden resolver ese problema de manera eficiente. Por ejemplo, dado el siguiente problema:

a = (λt . t 
    (F (λ f x . (f (f (f x))))) 
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

Cualquier humano con suficiente conocimiento sobre el cálculo lambda podrá notar que Fes la función "doble" para los números de la iglesia, que viene rápidamente con la solución que

 F = (λ a b c . (a b (a b c)))

Mi pregunta es: si ese problema es indecidible, ¿cómo pueden los humanos resolverlo rápida y fácilmente?

computability MaiaVictor
fuente

"los humanos pueden resolver ese problema de manera eficiente" - cita requerida. ¿Cuál es tu evidencia de eso? Mostrar un ejemplo en el que puede resolverlo de manera eficiente no significa que pueda resolverlo de manera eficiente para todas las instancias del problema. No puede probar que "X es verdadero para todas las X" mostrando un ejemplo de X donde X es verdadero.

Un problema es indecidible significa que no existe un algoritmo que responda correctamente "sí" o "no" para cada instancia del problema. No implica que uno pueda encontrar un algoritmo que resuelva algunas (o muchas) instancias del problema. [Je. Como DW respondió mientras escribía este comentario.]

Rick Decker

¿Resuelve este problema? Ni siquiera entiendo este problema.

MikeTheLiar

La forma en que lo entendí es esta: esa solución es ad hoc. Cada instancia del problema tiene uno, en la mayoría de los casos no es tan fácil de motivar como en su ejemplo, pero siempre puede decir 'si obtiene la instancia X, salida Y', ya que un algoritmo solo puede juzgarse sobre la base de la corrección. pero codificar todas estas soluciones de esta manera no produce un procedimiento finito (que es el único tipo razonable y, por lo tanto, lo que generalmente se entiende). Alternativamente, para que un problema sea decidible no se le permite ver qué instancia se da antes de elegir la estrategia del algoritmo.

Vandermonde

Además, esta es la razón por la cual solo los problemas con un número infinito de instancias generalmente se consideran o se llaman así, ya que de lo contrario podría enumerar todas las soluciones como se indica arriba.

Vandermonde

Respuestas:

Los humanos pueden resolver algunos casos de ese problema de manera eficiente, pero no hay razón para creer que los humanos puedan resolver todos los casos de manera eficiente. Mostrar una instancia que un humano puede resolver de manera eficiente no implica que los humanos puedan resolver todas las instancias de manera eficiente.

Indecidible significa "no existe un algoritmo que pueda resolver todas las instancias y que siempre termine". Todavía podría haber un algoritmo que pueda resolver algunas instancias , incluso para un problema indecidible.

Entonces no hay contradicción.

DW
fuente

@srvm, sí, significa eso. Por ejemplo, aquí hay un ejemplo estúpido de un algoritmo de computadora: "si la entrada es exactamente el ejemplo dado en su pregunta, entonces salga F = (λ a b c . (a b (a b c)))y pare". Ese es un algoritmo informático que resuelve el problema para algunos casos (en particular, para exactamente 1 caso). Sí, está bien, hacer una nueva pregunta como esa parece ser lo correcto. Como de costumbre, díganos qué investigación ha hecho en la pregunta (debe hacer un poco antes de preguntar).

Donde los problemas realmente difíciles son afirmaciones de que incluso en problemas completos de NP, la mayoría de los casos se pueden resolver fácilmente. Esto coincide con mi experiencia. Por lo general, hay características del problema que hacen que (al menos parte de) la solución sea obvia. Los difíciles están cuidadosamente equilibrados entre el éxito y el fracaso, pero no hay muchos de esos.

Ross Millikan

@srvm si lo piensa, resolver problemas difíciles como estos en casos especiales es exactamente lo que tiene que hacer un optimizador.

Cort Ammon

@srvm: Un excelente ejemplo de un problema indecidible que hacemos que las computadoras resuelvan casi todos los días es el problema de detención. Sabemos que el problema de la detención es indecidible, pero aún persistimos en escribir linters, analizadores estáticos y compiladores que intentan detectar bucles infinitos no deseados. Cómo lo hacemos es por "regla general". Es decir, sabemos por experiencia humana (no algoritmo) que ciertos tipos de código entran en un bucle infinito. Entonces le pedimos a la computadora que busque los casos que conocemos. Sabemos que tales programas nunca detectarán todos los errores. Pero es mejor que nada.

slebetman

para la posteridad, un nuevo enlace a: Dónde están los problemas realmente difíciles

Alex Moore-Niemi

Como señala uno de los comentarios, uno debe tener en cuenta que hay algunos algoritmos bastante buenos para resolver la coincidencia de patrones de orden superior en la práctica (como revelará una búsqueda rápida en Google ).

No conozco ninguno que resuelva este problema en particular, pero este problema de "duplicación" se siente más cercano al campo de la síntesis de programas . Creo que existen sistemas de síntesis de programas que pueden abordar este tipo de problema.

Sin embargo, es fácil crear ejemplos que hagan que esos sistemas se ahoguen, y parece que los humanos son particularmente buenos en este tipo de problemas. Crear algoritmos que estén más cerca de los humanos en su capacidad para resolver este tipo de problemas es el ámbito de la prueba automática de teoremas y la inteligencia artificial (para los intentos más ambiciosos / poco realistas).

cody
fuente

Los humanos siempre intentan resolver el problema con su propio conocimiento, por lo que los humanos desarrollan algún algoritmo para resolver el problema con algunas instancias de problema. Por lo tanto, los humanos desarrollan un algoritmo, pero no hay certeza de que el algoritmo particular pueda resolver cada problema. Por lo tanto, ningún algoritmo puede resolver todos los problemas, pero todavía hay algún problema que puede resolver el ser humano a pesar de que no hay un algoritmo perfecto para eso, como podemos decir que sabemos cómo resolver un problema pero no tenemos un algoritmo .

fuente

¿No es esto solo una paráfrasis de la respuesta existente? Sé que he criticado la mayoría de sus respuestas, por lo que lo siguiente puede parecer poco sincero, pero no lo es. Realmente es genial que quieras contribuir al sitio. Sería realmente genial si pudieras ayudarnos a responder algunas de nuestras 2500 preguntas sin respuesta , en lugar de preguntas en las que ya tenemos una respuesta que dice todo lo que quieres decir. ¡Gracias!

David Richerby