Problemas indecidibles en geometría

Question

¿Existen (muchos) problemas algorítmicamente indecidibles en la geometría computacional (combinatoria/discreta)?

Actualización: las fichas de Wang responden a la pregunta con "cualquiera". (He pasado un poco por alto contarlas cuando estaba buscando las respuestas a problemas generales indecidibles). Pero sigo sospechando que no hay muchos ejemplos que surjan naturalmente en la geometría combinatoria/discreta. Y, por supuesto, estoy interesado en cualquier ejemplo de este tipo. No cuento reformulaciones artificiales de problemas enunciados (por los autores) en diferentes escenarios.

Por ejemplo, durante bastante tiempo estuvo abierto el tema de si los gráficos de STRING (gráficos de intersección de curvas en el plano) son reconocibles. Sin embargo, resultó que sí lo son. Si la respuesta fuera contraria, sería un ejemplo de problema que busco.

(Permítanme también excluir los problemas muy similares a las baldosas de Wang, si es que los hay).

Answer 1

El problema consiste en determinar si dos 4manifolds, dados como complejos simpliciales, son homeomorfos. Markov demostró que esto es indecidible. (Algunas teorías de la física implican una suma sobre tales variedades, un término aditivo para cada clase de homeomorfismo, y esto llevó a especular que la física era no computable en algún sentido [Geroch y Hartle 1986]. No estoy seguro de cuál es la situación actual de esto).

Answer 2

Conozco vagamente dos ejemplos, pero no puedo aportar referencias.

El primero es el problema de los mosaicos de colores. Supongamos que nos dan una colección finita de cuadrados de igual tamaño, de manera que cada borde de cada cuadrado está coloreado. Se dice que la colección es un mosaico en el plano si se pueden organizar (posiblemente infinitas) copias de los cuadrados de la colección en un patrón de cuadrícula en el plano de tal manera que siempre que dos cuadrados son adyacentes a lo largo de un borde los colores de los bordes coinciden. Resulta que el problema de determinar cuándo una colección dada de cuadrados coloreados forma un mosaico en el plano contiene el problema de detención y, por lo tanto, es indecidible.

El segundo es el problema de determinar cuándo dos variedades trianguladas son equivalentes en homotopía. Un algoritmo para hacer esta determinación daría necesariamente una solución al problema de la palabra para los grupos, por lo que es indecidible.

Answer 3

Sí, los hay. Si quieres obtener una respuesta más informativa, quizá debas hacer una pregunta más informativa (como, por ejemplo, a qué círculo de problemas te refieres realmente...)