Języki jednoargumentowe rozpoznawane przez dwustronne deterministyczne automaty licznikowe

2dca (dwukierunkowe deterministyczne automaty licznikowe) (Petersen, 1994) może rozpoznać następujący jednoargumentowy język:

Czy jest jakiś inny nietrywialny, unary język rozpoznawany przez 2dca?

Zauważ, że nadal nie wiadomo, czy 2dca może rozpoznać ?$\mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace$

DEFINICJA: 2dca jest dwustronnym deterministycznym automatem skończonym z licznikiem. 2dca może sprawdzić, czy wartość licznika wynosi zero, czy też nie, i zwiększyć lub zmniejszyć wartość licznika o 1 w każdym kroku.

To tylko pomysł, który przyszedł mi do głowy podczas czytania Marvina L. Minsky'ego, „Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of Turing Machines”; w szczególności słynne twierdzenie Ia:

Twierdzenie Ia: Możemy przedstawić dowolną częściową funkcję rekurencyjną przez program działający na dwóch liczbach całkowitych S 1 i S 2 przy użyciu instrukcji I j postaci: (i) DODAJ 1 do S j i przejdź do I j 1 ( ii) odjąć 1 od S j , jeśli S j ≠ 0 i przejść do i J 1 , w przeciwnym razie przejdź do i j 2 Oznacza to, że możemy skonstruować taki program, który zaczyna się od S $f(n)$$S_1$$S_2$$I_j$
$S_j$$I_{j_1}$
$S_j$$S_j \neq 0$$I_{j_1}$$I_{j_2}$
i S 2 = 0 i w końcu zatrzymuje się z S 1 = 2 f ( n ) i S 2 = $S_1 = 2^n$$S_2 = 0$$S_1 = 2^{f(n)}$$S_2 = 0$

Jeśli masz dwustronną DFA z jednym licznikiem nad (semi) taśmy nieskończonej gdzie wejście jest podany w jednoskładnikowa: potem DFA może:$\$1^{2^n}000...$

1. przeczytaj jednoargumentowe wejście (i zapisz je w liczniku);
2. pracować na części taśmy i użyć odległości od 1 s jako drugiego licznika.$0^\infty$$1$

dzięki czemu może symulować maszynę z dwoma licznikami Turing.

Teraz, jeśli masz funkcję rekurencyjną która działa w czasie T ( n ) na standardowej maszynie Turinga, dwukierunkowy DFA z jednym licznikiem, który rozpoczyna się na skończonej taśmie $ 1 mln$f(n)$$T(n)$ $\$1^m\$ \;$(gdzie i T ′ ( n ) ≫ T ( n ) ) może:$m = 2^n3^{T'(n)}$$T'(n) \gg T(n)$

1. przeczytaj jednoargumentowe wejście (i zapisz je w liczniku);
2. powrót do lewego skrajnego symbolu;
3. dziel licznik przez 3, aż licznik zawiera w ten sposób: przejdź w prawo zapętlając od stanów q z 0 , q z 1 , q z 2 i odejmując 1; jeśli licznik osiągnie 0 w stanie q z 0, przejdź do symbolu znajdującego się najbardziej na lewo, dodając +1 i kontynuuj pętlę podziału, w przeciwnym razie dodaj 1 (jeśli jest w stanie q z 1 ) lub 2 (jeśli jest w stanie q z $2^n$$q_{z_0}, q_{z_1}, q_{z_2}$$q_{z_0}$$q_{z_1}$$q_{z_2}$ ) i przejdź do dodawania symbolu na lewo + 3 (tj. Odzyskaj poprzednią wartość licznika niepodzielnego przez 3) i przejdź do kroku 4 .;
4. w tym momencie licznik zawiera $2^n$ ;
5. obliczyć używając przestrzeni T ' ( n ) dostępnej po prawej stronie jako drugiego licznika (wartość drugiego licznika jest odległością od skrajnie lewego symbolu $ ).$2^{f(n)}$$T'(n)$$\$$

Tak więc dzięki specjalnemu kodowaniu wejściowemu opisanemu powyżej, które zapewnia mu wystarczającą ilość miejsca na skończonej taśmie, dwukierunkowy DFA z jednym licznikiem i jednoargumentowym alfabetem może obliczyć każdą funkcję rekurencyjną.

Jeśli podejście jest prawidłowe, warto zastanowić się, jak wybrać lub kiedy wystarczy wybrać duży nieparzysty k ≫ 2 i zakodować dane wejściowe jako 1 m , m = 2 n k $T'(n) \gg T(n)$$k \gg 2$$1^m$$m = 2^n k^n$

Przez nietrywialne zakładam, że masz na myśli język L, który nie może być zaakceptowany przez 1dca. Oto wydaje się taki język:

CENTRUM = {w | w jest powyżej {0,1} * i w = x1y dla niektórych x, y takich, że | x | = | y |}

Ten język nie może być zaakceptowany przez 1dca, ale MOŻE być zaakceptowany przez 1nca. Może być zaakceptowany przez 2dca. Szczegóły pozostawia się jako ćwiczenia.