¿Puede una máquina de dos contadores decidir

Puede una máquina estándar de dos contadores ( ) con las siguientes instrucciones: $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

decide el siguiente idioma:

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

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

(la entrada se carga inicialmente en el contador ) ?. $c_1$

¿Sigue siendo un problema abierto? (cf. Rich Schroeppel, "Una máquina de dos contadores no puede calcular " [1972]) $2^N$

fl.formal-languages counter-automata Marzio De Biasi
fuente

Estoy tratando de comprender los resultados más importantes del papel y estoy muy sorprendido por la progresión aritmética Teorema en la página 12. Supongamos que

es el mayor divisor impar de

. Entonces, ¿qué serían

? Probablemente he entendido mal algo en alguna parte ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Ahora lo miraré, pero ¿estás seguro de que "el divisor impar más grande de N" es computable por un 2CM?

Marzio De Biasi

@domotorp: por cierto, hice la misma pregunta también sobre mathoverflow , pero no obtuve nuevas ideas

Marzio De Biasi

Creo que si sigues dividiendo N entre 2 hasta que puedas, obtendrás el divisor impar más grande y esto debería ser sencillo de hacer.

domotorp

Bien, creo que si

(con

impar) y

es la mayor potencia de dos mayor que

, podemos establecer

. Informalmente, si

tiene bits

, puede expandir de forma segura el bit más significativo de

agregando

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}$ y el resultado cambiará por

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Respuestas:

El problema se ha resuelto en:

Oscar H. Ibarra, Nicholas Q. Trân, Una nota sobre programas simples con dos variables, Theoretical Computer Science, Volumen 112, Número 2, 10 de mayo de 1993, Páginas 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Deje que sea la clase de idiomas reconocidos por las máquinas de dos contadores. $TV$

Teorema 3.3 : para cualquier entero fijo , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Nota: es extraño que en el artículo de Ibarra y Tran

Teorema 3.4 Sea una función total con rango infinito y tal que la relación para todos no se cumple para ningún triple ; entonces no puede ser calculado por ninguna máquina de dos contadores. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

está probado y los autores dicen que se ha derivado de una forma ligeramente diferente en:

IM Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), ruso, Álgebra i Logika 1 (1963) 42-51

pero no cites el artículo de Rich Schroeppel (1972) en el que también se deriva el teorema ... :-)

Marzio De Biasi
fuente

No estoy seguro de que sea extraño que un artículo de veinte años no sea citado: presumiblemente los autores no lo sabían y los árbitros tampoco.

David Richerby

@DavidRicherby: Me gustaría ver cómo el teorema en Schroeppel (1972) difiere del correspondiente en Barzdin (1963) :-) ... pero no tengo acceso al documento de Barzdin

Marzio De Biasi