Przypuszczenie o dwóch automatach liczników

Chciałbym udowodnić (lub obalić) następującą hipotezę:

Przypuszczenie : automaty z dwoma licznikami (2CA) nie mogą zdecydować o następującym języku:

n $L = \{ n \mid$ trójskładnikowej i binarnej reprezentacji ma zarówno parzystą, jak i nieparzystą długość$n$$\}$

2CA może łatwo sprawdzić, czy reprezentacja binarna ma parzystą, czy nieparzystą długość (po prostu dziel dzielenie przez dwa i aktualizuj flagę „parzystej długości” po każdym dzieleniu); w ten sam sposób może sprawdzić, czy trójskładnikowa reprezentacja ma parzystą, czy nieparzystą długość (wystarczy dzielić przez trzy i aktualizować flagę „parzystej długości” po każdym podziale).

Ale aby obliczyć jeden z nich, musi zniszczyć swój wkład i nie może go odzyskać, aby obliczyć drugi; więc wydaje się, że nie ma sposobu, aby zdecydować, .$L$

Czy znasz technikę, której można użyć do udowodnienia przypuszczenia?
Czy możesz obalić domysł, budując 2CA, który decyduje o ? $L$

Wypróbowałem to samo podejście, którym podążyła Ibarra, aby udowodnić, że 2CA nie może zdecydować$\{n^2\mid n \geq 1\}$ , ale wydaje się to niewłaściwa droga.

Uwaga : dla uproszczenia 2CA jest równoważne programowi z jedną zmienną która początkowo zawiera dane wejściowe i następujący zestaw instrukcji:$c$

• INC : dodaj jeden do zmiennej;
• DEC : zmniejszenie (tylko jeśli jest większe od zera);$c$
• JZ $lab$ c l a b : jeśli wynosi zero, przejdź do etykiet, w przeciwnym razie kontynuuj;$c$$lab$
• MUL$K$ : pomnóż $c$ przez kosztowną $K$ ;
• $K [, lab_0, lab_1,...,lab_{K-1}]$$c$$K$$c$$c = \lfloor c / K \rfloor$$c \bmod K$
• Laboratorium GOTO$lab$ : skok bezwarunkowy;
• HALT Zaakceptuj | Odrzuć : zatrzymaj i zaakceptuj lub zatrzymaj i odrzuć.

Na przykład program sprawdzający, czy binarna reprezentacja ma parzystą długość, to:$n$

   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject

(możemy zbudować równoważny 2CA)

Dlatego ludzie ciągle mnie nakłaniają do opublikowania tego, mimo że rozwiązuje to tylko uproszczoną wersję problemu. W porządku :)

Na koniec przedstawię trochę tego, czego nauczyłem się z pracy Ibarry i Trâna, i dlaczego ta metoda załamuje nasz ogólny problem, ale być może nadal dostarcza użytecznych informacji.

Ale najpierw przyjrzymy się prostszemu problemowi przy podejmowaniu decyzji o zestawie

trójskładnikowy i binarnym z 2 n mają zarówno nawet długość lub nieparzystej długości$L = \{ 2^n \mid$$2^n$$\}$

$2^n$$n$

$2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$$v_i$$v_2$$0$

$k$

$k$$v_2$$v_3$$v_5$

$2^{v_2}$$v_3$$v_5$

Oto kod do tego, w formacie asemblera podobnym do OP (właśnie dodałem zmienne do instrukcji). Właściwie to go nie testowałem, ponieważ nie mam z czym go uruchomić, ale uważam to za formalność: automaty 3-licznikowe są dobrze znane jako kompletne Turinga i zdolne do konstruowania dowolnej funkcji obliczeniowej jednego z ich Wartości początkowe.

// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject

Następnym krokiem jest ponowne zakodowanie powyższego w wykładnikach automatu z jedną zmienną. Ponieważ wynik jest dość długi, opiszę tylko ogólną metodę, ale pełna wersja (nieco „zoptymalizowana” w punktach) znajduje się na mojej stronie.

                JZ vp, label
                DEC vp
next:           ...

staje się (w zasadzie podziel przez p, a następnie wykonaj czyszczenie, aby cofnąć, jeśli podział nie był nawet równy):

                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...

INC vpstaje się MUL p. Indywidualne JZi DECmożna je najpierw zmienić w połączoną formę. GOTO labeli HALT Rejectpozostają niezmienione.

HALT Acceptpozostałby niezmieniony, z wyjątkiem tego, że w naszym przypadku mamy jeszcze jedną ostateczną kontrolę: musimy upewnić się, że nie ma żadnych czynników pierwszych w liczbie innej niż 2,3 i 5. Ponieważ nasz szczególny automat 3-licznikowy zeruje go, używa, gdy akceptuje, jest to proste: wystarczy przetestować, że zmienna końcowa ma wartość 1, co można zrobić, przechodząc do kodu

                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept

Kod na mojej stronie ma również wstępną kontrolę, czy liczba nie jest zerowa, co właśnie zdałem sobie sprawę, że jest zbędne w przypadku kontroli zerowych v3, v5, no cóż.

Jak wspomniałem, powyższa metoda działa na uproszczony problem, ale tak naprawdę nie ma szans na działanie w przypadku problemu ogólnego, ponieważ: W ogólnym problemie dokładna wartość wykładnika każdej liczby pierwszej ma znaczenie przy podejmowaniu decyzji o jego ogólnym rozmiarze, a tym samym o jego długości ma w różnych podstawach. To znaczy że:

• Nie mamy „darmowych” liczb pierwszych do użycia dla liczników.
• Nawet jeśli nie mają wolne liczb pierwszych dla liczników, tak naprawdę nie ma sposobu, aby wyodrębnić wszystkie niezbędne informacje od nieskończenie wiele innych liczb pierwszych, których wykładnik wartości zrobić materia.

Zakończmy więc wyjaśnienie istoty ogólnej metody z powyższego powiązanego artykułu autorstwa Ibarry i Trâna ( wersja do pobrania za darmo ), aby udowodnić, że niektóre problemy nie są rozwiązane przez 2CA, i jak irytująco psuje się w naszym walizka.

$s$

Następnie analizują ten automat, aby stwierdzić, że mogą konstruować pewne ciągi arytmetyczne liczb, których zachowanie jest powiązane. Aby być precyzyjnym (niektóre z nich nie są określone jako twierdzenia, ale są dorozumiane w dowodzie obu ich dwóch głównych przykładów):

1. $v^x_i$$i$ $\leq s$$D>0$$x + n D$$n\geq 0$

2. $X$$s^2+1$$x\in X$$i$$v^x_i\leq s$$p, r\in X$$K_1,K_2$

   • $n\geq 0$$p + n K_1$$r + n K_2$

(Myśli:

• $x>s$$x\in X$
• Większość z nich powinna obowiązywać również w przypadku numerów odrzuconych , o ile odrzucenie następuje poprzez wyraźne wstrzymanie, a nie zakończenie.)

$D,K_1,K_2$$>s$

$K_1 = K_2 = 6^k$$k$$p$$r$$2^k$$3^k$$p + 6^k n$$q + 6^k n$

$K_1\neq K_2$