Uma máquina de dois contadores pode decidir ?

É possível dois contadores padrão ( ) com as seguintes instruções: $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

decida o seguinte idioma:

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

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

(a entrada é inicialmente carregada no contador )? $c_1$

Ainda é um problema em aberto? (cf. Rich Schroeppel, "Uma máquina de dois contadores não pode calcular " [1972]) $2^N$

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

Eu estou tentando compreender os resultados mais importantes do papel e eu estou realmente surpreso com a Aritmética Progressão Teorema na página 12. Suponha que

F (N)

$F(N)$ é o maior divisor ímpar de

N

$N$ . Então, o que

D

$D$ e

M

$M$ seriam? Provavelmente eu ter entendido mal algo em algum lugar ...

domotorp

Agora vou dar uma olhada, mas você tem certeza de que "o maior divisor ímpar de N" é computável por 2cm?

Marzio De Biasi

@domotorp: pela maneira que eu fiz a mesma pergunta também sobre mathoverflow , mas não obter novas idéias

Marzio De Biasi

Eu acho que se você continuar dividindo N por 2 até conseguir, obterá o maior divisor ímpar e isso deve ser fácil de fazer.

Domotorp

Ok, acho que se (com ímpar) e é a maior potência de duas maior que , é a maior potência de duas maior que , podemos definir , . Informalmente, se tiver bits, você poderá expandir com segurança o bit mais significativo de adicionando e o resultado será alterado por .

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}$

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Respostas:

O problema foi resolvido em:

Oscar H. Ibarra, Nicholas Q. Trân, uma nota sobre programas simples com duas variáveis, Ciência da Computação Teórica, Volume 112, Edição 2, 10 de maio de 1993, Páginas 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Permita que a seja a classe de idiomas reconhecida por máquinas de dois contadores. $TV$

Teorema 3.3 : para qualquer número inteiro fixo , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Nota: é estranho que no artigo de Ibarra & Tran

Teorema 3.4 Seja uma função total com alcance infinito e tal que a relação para todo não seja válida para nenhum triplo ; então não pode ser calculado por qualquer máquina de dois contadores. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

está provado e os autores dizem que foi derivado de uma forma ligeiramente diferente em:

IM Barzdin, Ob odnom klasse machin Turinga (minúsculo Minskogo), russo, álgebra e lógica 1 (1963) 42-51

mas não cite o artigo de Rich Schroeppel (1972), no qual o teorema também é derivado ... :-)

Marzio De Biasi
fonte

Não sei se é estranho que um artigo de vinte anos não seja citado: presumivelmente os autores não sabiam disso e nem os árbitros.

precisa saber é o seguinte

@DavidRicherby: Gostaria de saber como o teorema de Schroeppel (1972) difere do correspondente em Barzdin (1963) :-) ... mas não tenho acesso ao artigo de Barzdin

Marzio De Biasi