Um MPA (autômato multipebble) é um 2DFA (autômato finito determinístico de duas vias) que pode usar um número arbitrário de seixos (na verdade, no máximo seixos em uma determinada entrada - a entrada é gravada na fita entre as duas extremidades -markers como ). Durante o cálculo, um MPA pode detectar se o símbolo sob a cabeça tem uma pedra e, em seguida, pode colocar uma pedra (remova a pedra) se não houver pedra (uma pedra).
é um homomorfismo, onde é um símbolo e .
Para qualquer linguagem determinística sensível ao contexto não é difícil mostrar que existe um de modo que possa ser reconhecido por um MPA. Então, falando livremente, podemos dizer que
qualquer "problema" decidível por um DTM de espaço linear (máquina determinística de Turing) pode ser decidido por um MPA.
Isso também se aplica a qualquer idioma em ? Os MPAs podem decidir todas as linguagens determinísticas sensíveis ao contexto?
é o comprimento de .
é o símbolo de , onde.
.
fonte
Respostas:
Talvez você possa criar uma linguagem no DPSACE (n) que não possa ser reconhecida por um MPA com usando um argumento de diagonalização (provavelmente a ideia é semelhante à da resposta de Ben, mas não a expliquei):k=1
Suponha que no alfabeto você codifique um MPA usando uma lista de transições:Σ={0,1}
onde é o estado atual, é o símbolo atual, é o status do seixo, é o novo estado, é o novo estado do seixo, é a direção do movimento, é um marcador final).a p s ′ p ′ L | R #s a p s′ p′ L|R #
Uma máquina de Turing na entrada pode verificar se é uma descrição válida de um e simulá-la na entrada para etapas usando células, estendendo a entrada desta maneira:M x MPAx x 4|x| 6|x|+log|x|
Onde:
Se em etapas, o TM emitirá o oposto (se não interromper emitirá 0).MPAx 4|x| M M
Para grande o suficiente , as etapas de simulação de são maiores queque é maior que o comprimento de uma descrição completa da configuração do ; dessa maneira, se o não parar em etapas, temos certeza de que ele fará um loop para sempre.x>x0 4|x| 2|x|+2|x|log|x| MPAx MPAx 4|x|
Suponha que exista um que decida o mesmo idioma de ; ele sempre será interrompido e você poderá criar um "maior" que decida o mesmo idioma com (basta adicionar estados dum).MPAy L M MPAy′ y′>x0
Por construção, temos, que é uma contradição.MPAy′(y′)=1−M(y′)=1−MPAy′(y′)
fonte
Não. Contra-exemplo: o problema de parada para MPAs é decidível no espaço linear: se o MPA tiver N estados, precisaremos de | k | +2 bits de espaço para armazenar os locais dos seixos, registrar N bits para armazenar o estado atual e bits para armazenar um contador; se o contador alternar, a máquina simulada nunca será interrompida. Isso é linear em | k | (ignorando o espaço O (N \ log N) necessário para descrever a máquina), conforme necessário.log(N(|k|+2))+|k|+2
Como essa linguagem é decidível no espaço linear, também é expressável como um DCSL.
fonte