Kann eine Zwei-Zähler-Maschine

14

Kann eine Standardmaschine mit zwei Zählern ( ) die folgenden Anweisungen ausführen:c1,c2

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={n2n1}

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

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

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 N . Was wären dann D und M ? Wahrscheinlich habe ich irgendwo etwas falsch verstanden ...F(N)NDM
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 x ungerade) und 2 i die größte Potenz von zwei größer als N ist , 2 l die größte Potenz von zwei größer als x ist , können wir D = 2 i - 1 setzen , M = 2 l - 1 . Informell , wenn N hat i Bits, dann können Sie sicher das signifikanteste Bit erweitern N Zugabe j 2 i - 1N=2kxx2iN2lxD=2i1M=2l1NiNj2i1und das Ergebnis ändert sich um . j2l1
Marzio De Biasi

Antworten:

10

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 , L k = { n k | n 0 } T Vk2Lk={nkn0}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 ( a + b n ) = f ( a ) + c n für alle n 0 für kein Tripel ( a , b , c ) gilt ; dann kann f von keiner Maschine mit zwei Zählern berechnet werden. ff(a+bn)=f(a)+cnn0(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