Ich möchte folgende Vermutung beweisen (oder widerlegen):
Vermutung : Ein Zwei-Zähler-Automat (2CA) kann die folgende Sprache nicht bestimmen:
n } der ternären und der binären Darstellung von hat sowohl gerade als auch ungerade Länge
Ein 2CA kann leicht überprüfen, ob die Binärdarstellung eine gerade oder ungerade Länge hat (teilen Sie einfach weiter durch zwei und aktualisieren Sie nach jeder Unterteilung ein "gerade Länge" -Flag). Auf die gleiche Weise kann geprüft werden, ob die ternäre Darstellung eine gerade oder ungerade Länge hat (einfach durch drei teilen und nach jeder Unterteilung ein Flag "gerade Länge" aktualisieren).
Aber um eines von ihnen zu berechnen, muss es seine Eingabe zerstören und kann es nicht wiederherstellen, um das andere zu berechnen; so scheint es, dass es keine Möglichkeit gibt, zu entscheiden .
Kennen Sie eine Technik, mit der die Vermutung bewiesen werden kann?
Oder können Sie die Vermutung widerlegen, dass ein 2CA entsteht, der entscheidet ?
Ich habe den gleichen Ansatz wie Ibarra versucht, um zu beweisen, dass ein 2CA sich nicht für , aber es scheint nicht der richtige Weg zu sein.
Hinweis : Der Einfachheit halber entspricht ein 2CA einem Programm mit einer Variablen , die anfänglich die Eingabe und den folgenden Befehlssatz enthält:
- INC : füge eins zur Variablen hinzu;
- DEC : Dekrementiere (nur wenn es größer als Null ist);
- JZ- c l a b : Wenn Null ist, springen Sie zum Etikett- andernfalls fahren Sie fort.
- MUL c K : Multipliziere mit dem Costanten ;
- DIV : dividiere durch die Konstante und speichere den Quotienten zu ( ); evtl. je nach Rest zu verschiedenen Labels springen ( );
- GOTO : bedingungsloser Sprung;
- HALT Accept | Reject : anhalten und annehmen oder anhalten und ablehnen.
Ein Programm zum Überprüfen, ob die Binärdarstellung von gerade Länge hat, lautet beispielsweise:
loop: JZ even // test if n = 0
DIV 2
JZ odd // test if n = 0
DIV 2
GOTO loop
even: HALT Accept
odd: HALT Reject
(Wir können eine äquivalente 2CA bauen)
quelle
Antworten:
Daher fordern mich die Leute immer wieder auf, dies zu posten, obwohl dies nur eine vereinfachte Version des Problems löst. Alles klar :)
Am Ende werde ich einen Teil dessen anführen, was ich aus der Arbeit von Ibarra und Trân gelernt habe, und warum diese Methode unser allgemeines Problem auflöst, aber vielleicht noch einige nützliche Informationen liefert.
Aber zuerst schauen wir uns das einfachere Problem an, bei dem wir versuchen, die Menge zu bestimmen
2 n }L={2n∣ der ternären und der binären Darstellung von haben beide eine gerade oder ungerade Länge2n }
Beachten Sie, wie dies anstelle von wie im ursprünglichen Problem hat. Insbesondere wenn die eingegebene Zahl keine Zweierpotenz ist , möchten wir sie ablehnen, anstatt zu versuchen, ihre Länge in einer beliebigen Basis zu berechnen. n2n n
Dies vereinfacht die Sache erheblich: Wenn die ursprüngliche Zahl als , müssen wir für alle außer nur überprüfen dass sie alle .v i v 2 02v23v35v57v7... vi v2 0
Dies ermöglicht es uns, dieses vereinfachte Problem zu lösen, indem wir eine Umhüllung der alten Methode (von Minsky, nehme ich an) zum Codieren des Zustands eines Zählerautomaten in die Exponenten der Primfaktorisierung der einzelnen Variablen eines Multiplikations- / Divisionsautomaten verwenden. Das entspricht, wie oben im OP vermerkt, einem 2-Zähler-Automaten.k
Zuerst brauchen wir einen Counter-Automaten zum Wickeln. Wir werden 3 Zähler mit den Namen , und .v 2 v 3 v 5k v2 v3 v5
Der Automat akzeptiert iff für die anfänglichen Zählerwerte, wenn die ternären und binären Darstellungen von beide eine gerade oder ungerade Länge haben und sowohl als auch Null sind. Wenn es akzeptiert, setzt es zuerst alle seine Zähler auf Null. v 3 v 52v2 v3 v5
Hier ist ein Code dafür in einem Assembler-Format, das dem OP ähnelt (ich habe den Anweisungen gerade Variablen hinzugefügt). Ich habe es nicht wirklich getestet, da ich nichts zu tun habe, aber ich halte dies für eine Formalität: 3-Zähler-Automaten sind dafür bekannt, vollständig zu sein und in der Lage zu sein, jede berechenbare Funktion von einer von ihnen zu konstruieren Anfangswerte.
Der nächste Schritt besteht dann darin, das Obige in die Exponenten eines einzelnen variablen Automaten umzucodieren. Da das Ergebnis ziemlich lang ist, beschreibe ich nur die allgemeine Methode, aber auf meiner Website befindet sich eine Vollversion (an Stellen leicht "optimiert").
wird (im Grunde durch p dividieren und dann aufräumen, um rückgängig zu machen, wenn die Teilung nicht gerade war):
INC vp
wirdMUL p
. IndividuellJZ
undDEC
kann zunächst in die kombinierte Form geändert werden.GOTO label
undHALT Reject
sind unverändert.HALT Accept
wäre unverändert, mit der Ausnahme , dass wir noch in unserem Fall eine abschließende Kontrolle zu tun haben: müssen wir sicherstellen , dass keine Primfaktoren der Zahl gibt es andere als 2,3 und 5. Da unsere speziellen 3-Zähler Automaten Nullen die Zähler es verwendet, wenn es akzeptiert, ist dies einfach: Testen Sie einfach, dass die endgültige Variable 1 ist, was durch Springen zum Code erfolgen kannDer Code auf meiner Website hat auch eine erste Überprüfung, dass die Zahl nicht Null ist, was ich gerade festgestellt habe, ist redundant mit den v3, v5 Null-Überprüfungen, na ja.
Wie ich bereits erwähnte, funktioniert die obige Methode für das vereinfachte Problem, aber es hat wirklich keine Chance, für das allgemeine zu arbeiten, weil: Im allgemeinen Problem der genaue Wert des Exponenten jedes Prims für die Entscheidung seiner allgemeinen Größe und damit für seine Länge zählt hat in verschiedenen Basen. Das bedeutet, dass:
Lassen Sie uns also mit einer Erklärung des Kerns der allgemeinen Methode aus dem oben verlinkten Artikel von Ibarra und Trân ( frei herunterladbare Version ) abschließen, um zu beweisen, dass bestimmte Probleme von einem 2CA nicht lösbar sind , und wie es in unserem ärgerlich zusammenbricht Fall.
Erstens modifizieren sie jeden 2CA in eine "normale Form", in der die beiden Zähler in "Phasen" zwischen nur steigendem und nur fallendem Zähler wechseln, bis sie Null erreichen. Die Anzahl der Zustände diesen normalisierte Automat eine wichtige Rolle bei den Schätzungen spielt.s
Anschließend analysieren sie diesen Automaten und schließen daraus, dass sie bestimmte arithmetische Folgen von Zahlen konstruieren können, deren Verhalten miteinander verknüpft ist. Um genau zu sein (Einige davon werden nicht als Theoreme angegeben, sondern sind implizit im Beweis ihrer beiden Hauptbeispiele enthalten):
Wenn eine Menge mindestens akzeptierte Zahlen enthält, so dass es für jede Zahl eine Phase so dass , dann können wir und ganze Zahlen finden so dassX s2+1 x∈X i vxi≤s p,r∈X K1,K2
(Gedanken:
Für ihre eigenen Beispiele verwenden sie häufig auch die Tatsache, dass keine Primfaktoren . Um die Unmöglichkeit zu beweisen, leiten sie dann Widersprüche ab, indem sie zeigen, dass solche arithmetischen Folgen nicht existieren können.D,K1,K2 >s
In unserem Problem bricht ein Widerspruch mit dem zweiten Fall zusammen. Wenn wir , wobei groß genug ist, dass keine Zahl zwischen und durch oder teilbar ist , dann gibt es auch keine Potenzen von 2 oder 3 zwischen und , also werden sie entweder beide akzeptiert oder beide abgelehnt. k p r 2 k 3 k p + 6 k n q + 6 k nK1=K2=6k k p r 2k 3k p+6kn q+6kn
Punkt 1 kann immer noch als unmöglich gezeigt werden, da Potenzen von 2 und 3 meist immer weiter auseinander wachsen. Und ich glaube, ich kann den zweiten Fall unmöglich zeigen, wenn (ich habe @MarzioDeBiasi das Argument per E-Mail geschickt). Vielleicht könnte jemand diese Information nutzen, um die Form des Automaten weiter einzuschränken und daraus einen Widerspruch abzuleiten.K1≠K2
quelle