Un ejemplo de problema indecidible fácil de entender

Question

Estoy buscando un problema indecidible que pueda poner como ejemplo fácil en una presentación al público en general. Me refiero a fácil en el sentido de que las matemáticas que hay detrás se puedan describir, bueno, sin matemáticas, es decir, con analogías e intuiciones, evitando los tecnicismos.

Answer 1

"¿Son estos dos números reales (o funciones, o gramáticas, o enunciados matemáticos) equivalente?"
_(Véase también problema de palabras )_

"¿Se deduce esta afirmación de estos axiomas?"
(Hilbert's Problema de decisión )

"¿Este programa informático se detiene alguna vez?"
"¿Tiene este programa informático alguna vulnerabilidad de seguridad?"
"¿Este programa de ordenador hace <cualquier declaración no trivial>?"
_(El problema de detención de la que todas las propiedades semánticas puede reducirse)_

"¿Puede este conjunto de fichas de dominó embaldosar el plano?"
_(Ver Problema de los azulejos )_

"¿Acaso esto Ecuación diofantina tener una solución entera?"
_(Ver El décimo problema de Hilbert )_

"Dadas dos listas de cadenas, ¿existe una lista de índices tal que las concatenaciones de ambas listas sean iguales?"
(Ver Problema de correspondencia postal )

---

También hay una gran lista en wikipedia .

Answer 2

Creo que el Problema de correspondencia postal es un muy buen ejemplo de un problema indecidible simple que además es relativamente desconocido.

Dado un conjunto finito de tuplas de cadenas

(a , bba) X
(ab,  aa) Y
(bba, bb) Z

el problema es determinar si existe una secuencia finita de estas tuplas , permitiendo la repetición, tal que la concatenación de la primera mitad sea igual a la concatenación de la segunda mitad

(bba, bb) Z
(ab,  aa) Y
(bba, bb) Z
(a,  bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)

El único gran problema que tengo con este problema es que la única prueba de indecidibilidad que conozco se basa en la simulación de una máquina de Turing - sería bueno encontrar una versión alternativa más elemental.

Answer 3

"¿Este programa informático se detiene alguna vez?"

"¿Tiene esta ecuación alguna solución?" (por supuesto, te refieres a una ecuación polinómica con soluciones enteras, pero para una presentación al público en general, probablemente te puedes apañar con sólo "ecuación" y "soluciones").

Answer 4

Tal vez quiera comprobar esto:

Alan_Turing_y_los_problemas_indecidibles_en_las_matemáticas en fora.tv

¿cuáles son los problemas indecidibles más atractivos de las matemáticas? en mathoverflow

MagicSquare en mathworld.wolfram

Answer 5

Tal vez considerar algunos Azulejos Wang .