Me estoy preparando para una charla dirigida a estudiantes de matemáticas de pregrado y, como parte de ella, estoy considerando discutir el concepto de capacidad de decisión. Quiero dar un ejemplo de un problema que actualmente no sabemos que sea decidible o indecidible. Existen muchos problemas de...
Si se restringe Turing Machines a una cinta finita (es decir, para usar el espacio limitado ), entonces el problema de detención es decidible, esencialmente porque después de varios pasos (que pueden calcularse a partir del número de estados Q y S , y el tamaño del alfabeto), se debe repetir una...
Sé que es indecidible determinar si un conjunto de fichas puede enlosar el plano, como resultado de que Berger usa fichas de Wang . Mi pregunta es si también se sabe que es indecidible determinar si un solo mosaico dado puede enlosar el plano, un mosaico monoédrico . Si esto sigue sin resolverse,...
Es bien sabido que el problema de equivalencia es indecidible para los lenguajes generales sin contexto. Sin embargo, todas las pruebas de este hecho que conozco parecen involucrar algunas gramáticas ambiguas sin contexto. Por esta razón, me gustaría preguntar si se sabe si el problema sigue siendo...
Estoy interesado en el siguiente problema: dadas matrices enteras decide si cada producto infinito de estas matrices finalmente es igual a la matriz cero.UN1, A2, ... , AkA1,A2,…,AkA_1,A_2, \ldots, A_k Esto significa exactamente lo que crees que hace: diremos que el conjunto de matrices tiene la...
Es un resultado bien conocido que la pregunta ¿Una gramática libre de contexto genera un lenguaje regular? Es indecidible. Sin embargo, se vuelve decidible en un alfabeto unario, simplemente porque en este caso, las clases de lenguajes libres de contexto y regulares coinciden. Mi pregunta es...
Sé que es imposible decidir la equivalencia para el cálculo lambda sin tipo. Citando a Barendregt, HP El cálculo Lambda: su sintaxis y semántica. Holanda Septentrional, Amsterdam (1984). :ββ\beta Si A y B son disjuntos, conjuntos no vacíos de términos lambda que están cerrados en igualdad,...
Estoy tratando de resolver un problema en particular, y pensé que podría resolverlo usando la teoría de autómatas. Me pregunto, ¿qué modelos de autómatas tienen una contención decidible en tiempo polinómico? es decir, si tiene máquinas , puede probar si eficiente. L ( M 1 ) ⊆ L ( M 2 )METRO1,...
El problema de detención para las máquinas de Turing es quizás el conjunto canónico indecidible. Sin embargo, demostramos que hay un algoritmo que decide casi todas las instancias del mismo. Por lo tanto, el problema de detención se encuentra entre la creciente colección de quienes exhiben el...
Respuesta: no conocida. Las preguntas formuladas son naturales, abiertas y aparentemente difíciles; La pregunta ahora es una wiki comunitaria. Visión general La pregunta busca dividir los idiomas que pertenecen a la clase de complejidad PPP , junto con las máquinas de Turing de decisión (TM)...
Se sabe que muchos problemas lógicos (por ejemplo, problemas de satisfacción de varias lógicas modales) no son decidibles. También hay muchos problemas indecidibles en la teoría de algoritmos, por ejemplo, en la optimización combinatoria. Pero en la práctica, los heurísticos y los algoritmos...
¿Cuáles son los límites conocidos de la capacidad de decisión de la comparación de la tasa de crecimiento de las funciones de ? Estoy aquí pensando en la capacidad de decisión de preguntas como "¿Es x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?" o "¿Es 2 lg ∗ x ∈ O ( lg lg x ) ?".N→NN→N\mathbb{N} \to...
¿Cuál es el modelo computacional más simple para el cual el problema del vacío es indecidible? El problema de vacío para un modelo computacional (por ejemplo, autómata de estado finito, autómata de empuje alternativo, autómata cuántico de error acotado con un contador, LBA determinista, etc.) es...
El "nombre del juego de mayor número" le pide a dos jugadores que escriban un número en secreto, y el ganador es la persona que anotó el número mayor. El juego comúnmente permite a los jugadores escribir funciones evaluadas en un punto, por lo que también sería una cosa aceptable para...
Un sistema de adición de vectores (VAS) es un conjunto finito de acciones A⊂ZdA⊂ZdA \subset \mathbb{Z}^d . NdNd\mathbb{N}^d es el conjunto de marcas . Una carrera es una palabra no vacía de marcas m0m1…mnm0m1…mnm_0 m_1\dots m_n st ∀i∈{0,…,n−1},mi+1−mi∈A∀i∈{0,…,n−1},mi+1−mi∈A\forall i \in \{0,...
Respuesta: no conocida Muchas gracias a todos los que ayudaron a refinar esta pregunta y las definiciones asociadas. Las definiciones de esta wiki proporcionaron el punto de partida para la wiki TCS más reciente " ¿Contiene P lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la...
Hay problemas que son decidibles, hay algunos que son indecidibles, hay semidecidabilidad, etc. En este caso, me pregunto si un problema puede ser metadecidible. Esto significa (al menos en mi cabeza) que no podemos decir si es decidible o no. Tal vez se sabe que la capacidad de decisión es...
Considere una gramática arbitraria sin contexto sobre el alfabeto . A las producciones de esta gramática, agregue dos producciones fijas sin contexto : y . Llame a la gramática resultante que significa " aumentada con las producciones ".{ 0 , 1 , ¯ 0 , ¯ 1 } P ¯ 0 0 → ϵ ¯ 1 1 → ϵ G P G PsolsolG{ 0...
El teorema de Robertson-Seymour dice que cualquier familia GG\mathcal G de gráficas menores cerradas puede caracterizarse por un número finito de menores prohibidos. ¿Existe algún algoritmo que para una entrada GG\mathcal G dé salida a los menores prohibidos o es indecidible? Obviamente, la...
¿Cada lenguaje indecidible reconocible de Turing tiene un subconjunto NP-completo? La pregunta podría verse como una versión más fuerte del hecho de que cada lenguaje infinito reconocible de Turing tiene un subconjunto infinito