Equivalencia de los problemas de marco y de parada
Autores: Dietrich, Eric; Fields, Chris
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Equivalencia de los problemas de marco y de parada
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Problema de marco de dominio abierto
Problema de detención
Indecidible
Problema de identificación del sistema
Problema de fundamentación de símbolos
Problema de decisión cuántica
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
El Problema del Marco en dominio abierto es el problema de determinar qué características de un entorno de tarea abierto necesitan ser actualizadas después de una acción. Aquí demostramos que el Problema del Marco en dominio abierto es equivalente al Problema de Detención y, por lo tanto, es indecidible. Discutimos otros dos problemas en dominio abierto estrechamente relacionados con el Problema del Marco, el problema de identificación del sistema y el problema de fundamentación de símbolos, y mostramos que también son indecidibles. Luego reformulamos el Problema del Marco como un problema de decisión cuántica, y demostramos que es indecidible por cualquier computadora cuántica finita.
Descripción
El Problema del Marco en dominio abierto es el problema de determinar qué características de un entorno de tarea abierto necesitan ser actualizadas después de una acción. Aquí demostramos que el Problema del Marco en dominio abierto es equivalente al Problema de Detención y, por lo tanto, es indecidible. Discutimos otros dos problemas en dominio abierto estrechamente relacionados con el Problema del Marco, el problema de identificación del sistema y el problema de fundamentación de símbolos, y mostramos que también son indecidibles. Luego reformulamos el Problema del Marco como un problema de decisión cuántica, y demostramos que es indecidible por cualquier computadora cuántica finita.