¿Cuál es el modelo computacional más simple para el cual el problema del vacío es indecidible?

¿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 determinar si, para una máquina determinada, el lenguaje reconocido / definido por esta máquina esta vacio. ¡Aquí la descripción de la máquina debe ser finita!

Sé que la palabra "más simple" es un poco vaga. Podría haber más de una respuesta para algunos modelos computacionales incomparables.

Como comentario especial, creo que la pregunta se volvería más interesante al centrarse en alfabetos unarios y binarios por separado.

Tenga en cuenta que hay muchos modelos computacionales para los cuales el problema de detención es decidible, pero el problema del vacío (y algunos otros problemas) es (son) indecidibles, por ejemplo, autómatas lineales (LBA) .

Probablemente ya tienes estos en tu bolso :-)

• Máquina bidireccional de un contador sobre alfabeto unario (Minsky61).
• Contadores débiles de dos vías (el contador no tiene ningún efecto en el cálculo pero la máquina se detiene si el contador llega a cero) [1].
• Quantum one counter autómatas [2].

Con alfabetos binarios, el vacío sigue siendo indecidible para:

• Máquinas unidireccionales con un contador ilimitado y una tienda pushdown que hace como máximo una inversión [3].

• Máquinas bidireccionales autómatas finitos deterministas con múltiples contadores de inversión (incluso en un lenguaje acotado) [3].

• Sin estado (las transiciones dependen solo del símbolo escaneado) Autómatas finitos deterministas bidireccionales y bidireccionales incluso cuando cada cabezal realiza una sola inversión en la cinta de entrada [4].

Editar : en el límite:

• (Problema abierto) ¿Es el problema del vacío decidible para autómatas finitos no deterministas bidireccionales con un contador limitado de inversión sobre lenguajes no limitados? (sobre idiomas delimitados es decidible [5])

[1] Tat-colgado Chan. En máquinas de mostrador débiles bidireccionales . Teoría de sistemas matemáticos 01/1987;
[2] Richard F. Bonner, Rusins ​​Freivalds y Maksim Kravtsev. 2001. Autómatas finitos cuánticos versus probabilísticos unidireccionales con contador . En Actas de la 28ª Conferencia sobre tendencias actuales en teoría y práctica de la informática Piestany: teoría y práctica de la informática (SOFSEM '01), Leszek Pacholski y Peter Ruzicka (Eds.). Springer-Verlag, Londres, Reino Unido, Reino Unido, 181-190.
[3] Oscar H. Ibarra. 1978. Máquinas multicounter limitadas por inversión y sus problemas de decisión . J. ACM 25, 1 (enero de 1978), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin,Sobre autómatas de múltiples cabezas sin estado: Jerarquías y el problema del vacío , Theoretical Computer Science, Volumen 411, Número 3, 6 de enero de 2010, Páginas 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. Sobre los problemas de vacío para nfa bidireccional con un contador limitado por inversión . En proc. Decimotercero Int. Symp. sobre Algoritmos y Computación (2002)