Kann eine Zwei-Zähler-Maschine

Kann eine Standardmaschine mit zwei Zählern ( ) die folgenden Anweisungen ausführen: $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

Entscheide dich für folgende Sprache:

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

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

(der Eingang wird zunächst in den Zähler geladen ). $c_1$

Ist es immer noch ein offenes Problem? (vgl. Rich Schroeppel, "Eine Maschine mit zwei Zählern kann nicht berechnen " [1972]) $2^N$

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

Ich versuche , die wichtigsten Ergebnisse des Papiers zu erreichen , und ich bin wirklich von der arithmetischen Progression Satz auf Seite 12. Es sei überrascht

ist die größte ungerade Teiler von

. Was wären dann

und

? Wahrscheinlich habe ich irgendwo etwas falsch verstanden ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Jetzt werde ich es mir ansehen, aber sind Sie sicher, dass "der größte ungerade Teiler von N" von einem 2CM berechenbar ist?

Marzio De Biasi

@domotorp: übrigens stellte ich die gleiche Frage auch auf Mathoverflow , bekam aber keine neuen Ideen

Marzio De Biasi

Ich denke, wenn Sie N durch 2 teilen, bis Sie können, erhalten Sie den größten ungeraden Divisor, und dies sollte einfach zu tun sein.

Domotorp

Ok, ich denke, wenn

(mit

ungerade) und

die größte Potenz von zwei größer als

, können wir

. Informell , wenn

hat

Bits, dann können Sie sicher das signifikanteste Bit erweitern

Zugabe

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}$ und das Ergebnis ändert sich um

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Antworten:

Das Problem wurde gelöst in:

Oscar H. Ibarra, Nicholas Q. Trân, Anmerkung zu einfachen Programmen mit zwei Variablen, Theoretical Computer Science, Band 112, Ausgabe 2, 10. Mai 1993, Seiten 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Sei die Klasse von Sprachen, die von Zwei-Zähler-Maschinen erkannt werden. $TV$

Theorem 3.3 : für jede ganze Zahl fixiert , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Hinweis: Es ist seltsam, dass in der Zeitung von Ibarra & Tran

Satz 3.4 Sei eine Gesamtfunktion mit unendlichem Bereich, und zwar so, dass die Beziehung für alle für kein Tripel ; dann kann von keiner Maschine mit zwei Zählern berechnet werden. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

wird bewiesen und die Autoren sagen, dass es in einer etwas anderen Form in abgeleitet wurde:

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

aber zitiere nicht Rich Schroeppels Arbeit (1972), in der der Satz auch abgeleitet ist ... :-)

Marzio De Biasi
quelle

Ich bin mir nicht sicher, ob es jemals merkwürdig ist, dass eine zwanzigjährige Zeitung nicht zitiert wird: Vermutlich wussten die Autoren davon nichts und die Schiedsrichter auch nicht.

David Richerby

@DavidRicherby: Ich würde gespannt sein , zu sehen , wie der Satz in Schroeppel (1972) unterscheidet sich von dem entsprechenden in Barzdin (1963) :-) ... aber ich keinen Zugriff auf das Papier der Barzdin haben

Marzio De Biasi