Solución:
“¿Son estos dos números reales (o funciones, o gramáticas o enunciados matemáticos) ¿equivalente?”
(Ver también problema verbal)
“¿Se sigue esta afirmación de estos axiomas?”
(Problema de Entscheidung de Hilbert)
“¿Este programa de computadora se detiene alguna vez?”
“¿Este programa de computadora tiene alguna vulnerabilidad de seguridad?”
“¿Este programa informático
(El problema de la detención, del cual se pueden reducir todas las propiedades semánticas)
“¿Puede este juego de fichas de dominó embaldosar el avión?”
(Ver problema de mosaico)
“¿Esta ecuación diofántica tiene una solución entera?”
(Ver el décimo problema de Hilbert)
“Dadas dos listas de cadenas, ¿hay 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.
Creo que el problema de la correspondencia postal es un muy buen ejemplo de un problema simple e indeciso que también 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, que permita la repetición, de manera 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 indecisión 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.
Quizás quieras comprobar estos:
Alan_Turing_and_Undecidable_Problems_in_Mathematics en fora.tv
¿Cuáles-son-los-problemas-indecidibles-más-atractivos-de-turing-en-matemáticas en mathoverflow
MagicSquare en mathworld.wolfram