Os 2dca (autômatos determinísticos bidirecionais de um contador) (Petersen, 1994) podem reconhecer a seguinte linguagem unária:
Existe alguma outra linguagem unária não trivial reconhecida pelos 2dca's?
Observe que ainda não se sabe se 2dca pode reconhecer ?
DEFINIÇÃO: Um 2dca é um autômato finito determinístico de duas vias com um contador. Um 2dca pode testar se o valor do contador é zero ou não e aumentar ou diminuir o valor do contador em 1 em cada etapa.
fl.formal-languages
automata-theory
counter-automata
Abuzer Yakaryilmaz
fonte
fonte
Respostas:
Essa é apenas uma idéia que me veio à mente ao ler Marvin L. Minsky, "Insolubilidade recursiva do problema de etiqueta de Post e outros tópicos da teoria das máquinas de Turing"; em particular o famoso teorema Ia:
Se você tiver um DFA bidirecional com um contador em uma fita (semi) infinita, em que a entrada é dada em unário: o DFA pode:$ 12n000 ...
para simular uma máquina completa de dois contadores da Turing.
Agora, se você tiver uma função recursiva que é executada no tempo T ( n ) em uma máquina de Turing padrão, um DFA bidirecional com um contador que inicia na fita finita $ 1 m $f(n) T(n) $1m$ (onde e T ′ ( n ) ≫ T ( n ) ) pode:m=2n3T′(n) T′(n)≫T(n)
Portanto, com a codificação de entrada especial descrita acima, que oferece espaço suficiente na fita finita, um DFA bidirecional com um contador e alfabeto unário pode calcular todas as funções recursivas.
Se a abordagem é correcta, seria interessante para raciocinar sobre como escolher ou quando é suficiente para escolher um grande ângulo diferente k » 2 e codificar a entrada como uma m , m = 2 n k nT′(n)≫T(n) k≫2 1m m=2nkn
fonte
Por não trivial, suponho que você queira dizer um idioma L que não pode ser aceito por um 1dca. Aqui parece haver uma linguagem assim:
CENTRO = {w | w está acima de {0,1} * e w = x1y para alguns x, y tais que | x | = | y |}
Este idioma não pode ser aceito por 1dca, mas PODE ser aceito por 1nca. Pode ser aceito por um 2dca. Os detalhes são deixados como exercício.
fonte