Qual é o modelo computacional mais simples para o qual o problema do vazio é indecidível?
O problema de vazio para um modelo computacional (por exemplo, autômato de estado finito, autômato de empilhamento alternado, autômato quântico de erro limitado com um contador, LBA determinístico, etc.) é determinar se, para uma determinada máquina, o idioma reconhecido / definido por esta máquina está vazia. Aqui a descrição da máquina deve ser finita!
Eu sei que a palavra "mais simples" é um pouco vaga. Pode haver mais de uma resposta para alguns modelos computacionais incomparáveis.
Como uma observação especial, acredito que a questão se tornaria mais interessante, concentrando-se nos alfabetos unários e binários separadamente.
Observe que existem muitos modelos computacionais para os quais o problema de parada é decidível, mas o problema de vazio (e alguns outros problemas) é (são) indecidível, por exemplo, autômatos limitados lineares (LBAs) .
fonte
Respostas:
Provavelmente você já os colocou na sua bolsa :-)
Com alfabetos binários, o vazio permanece indecidível para:
Máquinas unidirecionais com um contador ilimitado e um armazenamento de empilhamento que fazem no máximo uma reversão [3].
Autômatos finitos determinísticos de máquinas de duas vias com vários contadores limitados por reversão (mesmo em uma linguagem limitada) [3].
Sem estado (as transições dependem apenas do símbolo digitalizado) Autômatos finitos determinísticos de duas cabeças, mesmo quando cada cabeça faz apenas uma reversão na fita de entrada [4].
Editar : no limite:
[1] Chan pendurado por Tat. Em máquinas de balcão de duas vias fracas . Teoria dos Sistemas Matemáticos 01/1987;
[2] Richard F. Bonner, Rusins Freivalds e Maksim Kravtsev. 2001. Quantum versus autômato finito unidirecional probabilístico com contador . Nos Anais da 28ª Conferência sobre Tendências Atuais em Teoria e Prática da Informática Piestany: Teoria e Prática da Informática (SOFSEM '01), Leszek Pacholski e Peter Ruzicka (Eds.). Springer-Verlag, Londres, Reino Unido, Reino Unido, 181-190.
[3] Oscar H. Ibarra. 1978. Máquinas multicounter com limite de reversão e seus problemas de decisão . J. ACM 25, 1 (janeiro de 1978), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin,Sobre autômatos de cabeças múltiplas sem estado: Hierarquias e o problema do vazio , Teoria da Computação, Volume 411, Edição 3, 6 de janeiro de 2010, Páginas 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. Sobre os problemas de vazio para o nfa bidirecional com um contador limitado pela reversão . Em Proc. 13ª Int. Symp. em Algoritmos e Computação (2002)
fonte