Qual é o modelo computacional mais simples para o qual o problema do vazio é indecidível?

12

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) .

Abuzer Yakaryilmaz
fonte
Não siga a pergunta, mas é provável que o modelo mais simples seja trivial ou parecido com o da criança. você quis dizer exatamente o oposto, o menos simples? FSMs são muitas vezes consideradas como um dos modelos computacionais mais simples ...
vzn
Existe uma razão para acreditar que parada e vazio devem estar relacionados?
babou
@babou: Não! Apenas tentei apontar que o problema da decidibilidade do vazio é interessante para modelos restritos, mas o do problema de parada, o mais conhecido entre outros, não é.
Abuzer Yakaryilmaz 25/03

Respostas:

15

Provavelmente você já os colocou na sua bolsa :-)

  • Máquina bidirecional de balcão único sobre o alfabeto unário (Minsky61).
  • Contadores fracos bidirecionais (o contador não afeta o cálculo, mas a máquina pára se o contador atingir zero) [1].
  • Quantum one counter autômatos [2].

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:

  • (Problema em aberto) O problema do vazio é decidível para autômatos finitos não determinísticos de mão dupla com um contador limitado de reversão sobre idiomas não limitados? (em idiomas limitados é decidível [5])

[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)

Marzio De Biasi
fonte
Uau ... Existe um site com todas essas informações bem organizadas sobre decisões sobre autômatos e idiomas? Mesma pergunta para propriedades de fechamento.
21714
2
@babou: Eu não sei, mas concordo com você, um "Zoológico de Autômatos" ou um site como graphclasses.org seria muito útil (e eu também notei que provavelmente é o momento certo para um trabalho de pesquisa sobre o assunto) .
Marzio De Biasi