Czy maszyna z dwoma licznikami może zdecydować

Czy standardowa maszyna z dwoma licznikami ( ) może następujące instrukcje: $c_1,c_2$

1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

wybierz następujący język:

L = {n^{2} ∣ n \geq 1}

$L = \{ n^2 \mid n \geq 1 \}$

(wejście jest początkowo ładowane do licznika ) ?. $c_1$

Czy to wciąż problem otwarty? (por. Rich Schroeppel, „Maszyna dwóch liczników nie może obliczyć ” [1972]) $2^N$

fl.formal-languages counter-automata Marzio De Biasi
źródło

Staram się uchwycić najważniejszy wyniki papieru i jestem naprawdę zaskoczony arytmetyczny twierdzenia na stronie 12. Załóżmy, że

jest największym dziwne dzielnik

. Czym więc byłyby

? Prawdopodobnie coś gdzieś źle zrozumiałem ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Teraz przyjrzę się temu, ale czy jesteś pewien, że „największy nieparzysty dzielnik N” jest obliczalny przez 2CM?

Marzio De Biasi

@domotorp: nawiasem mówiąc, zadałem to samo pytanie również na matematycznym przepływie , ale nie otrzymałem nowych pomysłów

Marzio De Biasi

Myślę, że jeśli będziesz nadal dzielił N przez 2, dopóki nie będziesz w stanie, otrzymasz największy nieparzysty dzielnik i to powinno być łatwe do zrobienia.

domotorp

Ok, myślę, że jeśli

nieparzyste) i

jest największą mocą dwóch wartości większą niż

jest największą mocą dwóch osób większą niż

, możemy ustawić

. Nieformalnie, jeśli

ma bity

, możesz bezpiecznie rozwinąć najbardziej znaczący bit

dodając

N = 2^{k} x

$N = 2^k x$

x

$x$

2^{i}

$2^{i}$

N

$N$

2^{l}

$2^{l}$

x

$x$

D = 2^{i - 1}

$D=2^{i-1}$

M = 2^{l - 1}

$M = 2^{l-1}$

N

$N$

i

$i$

N

$N$

j 2^{i - 1}

$j 2^{i-1}$ a wynik zmieni się o

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Odpowiedzi:

Problem został rozwiązany w:

Oscar H. Ibarra, Nicholas Q. Trân, Notatka o prostych programach z dwiema zmiennymi, Theoretical Computer Science, tom 112, wydanie 2, 10 maja 1993, strony 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Niech będzie klasą języków rozpoznawanych przez maszyny z dwoma licznikami. $TV$

Twierdzenie 3.3 : Dla dowolnej stałej liczby całkowitej , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Uwaga: to dziwne, że w pracy Ibarra & Tran

Twierdzenie 3.4 Niech będzie całkowita funkcja nieskończonej gamy i takie, że stosunek dla wszystkich nie stosuje się do wszystkich potrójne ; wtedy nie może być obliczone przez żadną maszynę z dwoma licznikami. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

zostało udowodnione, a autorzy twierdzą, że został uzyskany w nieco innej formie w:

IM Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), rosyjski, Algebra i Logika 1 (1963) 42-51

ale nie cytuj pracy Richa Schroeppela (1972), w której również wywodzi się twierdzenie ... :-)

Marzio De Biasi
źródło

Nie jestem pewien, czy to dziwne, że nie zacytowano dwudziestoletniej gazety: przypuszczalnie autorzy nie wiedzieli o tym i sędziowie też tego nie wiedzieli.

David Richerby

@DavidRicherby: Byłbym ciekawy, jak różni się twierdzenie Schroeppela (1972) od analogicznego w Barzdinie (1963) :-) ... ale nie mam dostępu do pracy Barzdina

Marzio De Biasi