Une machine à deux compteurs peut-elle décider

Peut une machine standard à deux compteurs ( ) avec les instructions suivantes: $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

décidez de la langue suivante:

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

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

(l'entrée est initialement chargée dans le compteur )?. $c_1$

Est-ce toujours un problème ouvert? (cf. Rich Schroeppel, "Une machine à deux compteurs ne peut pas calculer " [1972]) $2^N$

fl.formal-languages counter-automata Marzio De Biasi
la source

Je suis en train de saisir les résultats les plus importants du papier et je suis vraiment surpris par le théorème progression arithmétique à la page 12. On suppose que

est le plus grand diviseur impair de

. Alors que seraient

? J'ai probablement mal compris quelque chose quelque part ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Maintenant, je vais l'examiner, mais êtes-vous sûr que "le plus grand diviseur impair de N" est calculable par un 2CM?

Marzio De Biasi

@domotorp: au fait j'ai aussi posé la même question sur mathoverflow , mais je n'ai pas eu de nouvelles idées

Marzio De Biasi

Je pense que si vous continuez à diviser N par 2 jusqu'à ce que vous le puissiez, vous obtiendrez le plus grand diviseur impair et cela devrait être simple à faire.

domotorp

Ok, je pense que si

(avec

impair) et

est la plus grande puissance de deux supérieure à

, nous pouvons définir

. Informellement, si

bits, vous pouvez étendre en toute sécurité le bit de

le plus significatif en ajoutant

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}$ et le résultat changera de

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Réponses:

Le problème a été résolu dans:

Oscar H. Ibarra, Nicholas Q. Trân, A note on simple programmes with two variables, Theoretical Computer Science, Volume 112, Numéro 2, 10 mai 1993, Pages 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Soit la classe de langages reconnue par les machines à deux compteurs. $TV$

Théorème 3.3 : Pour tout entier fixe , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Remarque: il est étrange que dans le document d'Ibarra & Tran

Théorème 3.4 Soit une fonction totale de portée infinie et telle que la relation pour tout ne soit valable pour aucun triple ; alors ne peut être calculé par aucune machine à deux compteurs. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

est prouvé et les auteurs disent qu'il a été dérivé sous une forme légèrement différente dans:

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

mais ne citez pas l'article de Rich Schroeppel (1972) dans lequel le théorème est également dérivé ... :-)

Marzio De Biasi
la source

Je ne suis pas sûr qu'il soit jamais étrange qu'un article de vingt ans ne soit pas cité: vraisemblablement les auteurs ne le savaient pas et les arbitres non plus.

David Richerby

@DavidRicherby: Je serais curieux de voir en quoi le théorème de Schroeppel (1972) diffère de celui de Barzdin (1963) :-) ... mais je n'ai pas accès à l'article de Barzdin

Marzio De Biasi