Berechnen wir die β-Funktion (Gedells β-Funktion) mit SymPy. Versuchen Sie zu diesem Zeitpunkt, die Anzahl der Gödel im Ergebnis so weit wie möglich zu reduzieren.
Da dieser Artikel auch als Übung für das NumPy-Array des Autors dient, gibt es außerdem Orte, an denen modische Vektorberechnungen zwangsweise durchgeführt werden.
Eine Funktion zum Decodieren beim Codieren einer Zeichenfolge natürlicher Zahlen in eine natürliche Zahl. Es wird genannt, weil es im Beweis von Godels Unvollständigkeitssatz (1931) erscheint.
Nehmen Sie Folgendes an:
Für eine natürliche Zahl $ l, m, i $ ($ m> 0,0 \ le i \ le n-1 $) ist die Funktion $ \ beta $
\beta(l,m,i) = \text{rem}(l,(i+1)m + 1)
Definiert in (rem ist eine normale Restoperation, normalerweise wird mod oder% verwendet) [^ 1].
[^ 1]: $ im + 1 $ ist positiv, daher kann rem normal berechnet werden.
Zu diesem Zeitpunkt ist für die konkret gegebene natürliche Zahlenfolge $ a = \ langle a_0, \ dots, a_ {n-1} \ rangle $ der Länge $ n \ ge 1 $ eine bestimmte natürliche Zahl $ l, m Sie können $ so berechnen, dass für $ 0 \ le i \ le n-1 $ $ \ beta (l, m, i) = a_i $ [^ 2]. Das heißt, $ (l, m) $ kann als natürliche Darstellung der Sequenz betrachtet werden (dh ** Godel-Zahl **). Es gibt auch eine Möglichkeit, ein Paar natürlicher Zahlen mit einer einzigen natürlichen Zahl zu codieren (siehe Anhang), was dazu führt, dass die natürliche Zahlenfolge als natürliche Zahl codiert wird. In der folgenden Diskussion werden wir fortfahren, ohne die Codierung / Decodierung des Paares anzugeben.
[^ 2]: Ich sage nichts über $ i $ größer als dieses.
Da der chinesische Restsatz (CRT) zur Berechnung von $ l $ erforderlich ist, verwenden wir SymPy, eine Python-Bibliothek mit der Funktion crt.
Da wir ein konkretes Beispiel benötigen, betrachten wir ein Beispiel für die Codierung eines Arrays mit der Länge n = 5`` a = [31, 5, 51, 0, 2].
>>> import numpy as np
>>> from sympy.ntheory.modular import crt
>>> a = [31, 5, 51, 0, 2]
>>> a
[31, 5, 51, 0, 2]
>>> n = len(a)
>>> n
5
Es ist praktisch, also konvertieren wir es in das NumPy-Array a_. Erstellen Sie außerdem ein Array von "a_" Indizes.
>>> a_ = np.array(a)
>>> a_
array([31, 5, 51, 0, 2])
>>> a_idx = np.arange(n)
>>> a_idx
array([0, 1, 2, 3, 4])
Nachdem Sie eine Richtlinie zur Berechnung für die Codierung angegeben haben, berechnen wir tatsächlich mit Python. Bei einer Folge von Zahlen wie oben lautet die Codierungsrichtlinie wie folgt:
--Berechnen Sie $ m $ auf irgendeine Weise, so dass sich jedes $ m_i $ gegenseitig ausschließt (+ bestimmte Bedingungen erfüllt). --Berechnen Sie $ l $ mit dem chinesischen Restsatz unter Verwendung der Tatsache, dass jedes $ m_i $ zueinander prim ist.
Im Allgemeinen wird der Boden zur Berechnung von $ m $ verwendet. Diese Methode macht $ m $ jedoch sehr groß. Dann ist $ l $ tendenziell groß. In diesem Artikel werde ich versuchen zu berechnen, indem ich $ m $ und schließlich $ l $ so klein wie möglich mache. Ich bin mir jedoch nicht sicher, ob dies das Minimum ist.
Im Folgenden wird es ausgedrückt als $ m_i = (i + 1) m + 1 $. Das heißt, die Definition der β-Funktion lautet $ \ beta (l, m, i) = \ text {rem} (l, m_i) $.
Der Wikipedia-Artikel "Gödel-Nummerierung für Sequenzen" ist etwas verwirrend, erklärt jedoch die schwächsten möglichen Bedingungen, die $ m $ erfüllen sollte, und ist hilfreich (nicht sicher, ob es die schwächste ist oder nicht). Wenn $ m $ die folgenden Bedingungen erfüllt, kann es dementsprechend für die korrekte Codierung übernommen werden.
i\mid m \quad (1\le i\le n-1) \\
a_i < m_i \quad (0\le i \le n-1)
Die erste Gleichung bedeutet, dass $ m $ ein gemeinsames Vielfaches von ** $ 1, \ dots, n-1 $ ** ist. Daher wird empfohlen, die ** minimalen gemeinsamen Vielfachen (LCM) $ m_0 $ Vielfachen ** von $ 1, \ dots, n-1 $ als Kandidaten für $ m $ aufzulisten und die kleinste zu finden, die die zweite Gleichung erfüllt. Wahrscheinlich. Lass es uns versuchen.
m0NumPy hat eine Zwei-Argument-Funktion lcm. Da dies ein sogenannter Ufunc ist, können Sie den LCM für ein Array mithilfe der "Reduce" -Methode berechnen. Ich werde es versuchen. Da wir das tiefgestellte Array $ [0,1, \ dots, n-1] $ früher erstellt haben, verwenden wir $ [1, \ dots, n-1] $ als Slice.
>>> m0 = np.lcm.reduce(a_idx[1:])
>>> m0
12
Eine manuelle Berechnung des $ 1,2,3,4 $ LCM beträgt sicherlich $ 12 $. Dieses Vielfache $ m $ von $ m_0 $ erfüllt immer die erste Gleichung.
Im nächsten Abschnitt berechnen wir $ \ {m_i \} $ für verschiedene $ m $. Hier erklären wir zuerst, wie es geht.
Für jedes $ m $ müssen Sie $ \ {m_i \} $ finden und mit $ \ {a_i \} $ vergleichen.
Ersteres ist $ \ {m_i \ mid 0 \ le i \ le n-1 \} = \ {(i + 1) m + 1 \ mid 0 \ le i \ le n-1 \} $ .. Da der Bereich von $ i $ mit dem zuvor definierten "a_idx" übereinstimmt, kann er sofort durch Array-Berechnung berechnet werden. Definieren Sie die gewünschte Funktion als m_i_seq.
>>> def m_i_seq(m): return (a_idx + 1) * m + 1
Wenn Sie versuchen, für "m = 12" zu berechnen, wird es so sein.
>>> mis = m_i_seq(12)
>>> mis
array([13, 25, 37, 49, 61])
(Mis ist ein Bild von $ m_i $ s)
m, das die Bedingungen erfülltLassen Sie uns nun $ m $ (ein Vielfaches von $ m_0 $) finden, das die zweite Gleichung der Bedingung erfüllt. Erstens ist $ \ {m_i \} $ für den Fall von $ m = m_0 = 12 $ "mis = [13 25 37 49 61]", wie zuvor berechnet. Der Vergleich zwischen diesem und $ \ {a_i \} $ kann auch sofort mit der Vektorberechnungsfunktion des NumPy-Arrays berechnet werden.
>>> a_ < mis
array([False, True, False, True, True])
Sie können sehen, dass dies für die beiden $ i $ nicht gilt.
Als nächstes verdoppeln wir $ m_0 $ und setzen $ m = 24 $. In diesem Moment,
>>> mis = m_i_seq(24)
>>> mis
array([ 25, 49, 73, 97, 121])
>>> a_ < mis
array([False, True, True, True, True])
Es wurde noch nicht eingerichtet. Dies passiert, wenn $ m = 36 $.
>>> mis
array([ 37, 73, 109, 145, 181])
>>> a_ < mis
array([ True, True, True, True, True])
Es ist alles in Ordnung, weil alles "wahr" ist. Nehmen Sie dieses $ m = 36 $ an.
Wenn Sie sich wie oben beschrieben für $ m $ entscheiden, können Sie beweisen, dass die beiden unterschiedlichen Elemente von $ \ {m_i \} $ elementar zueinander sind. Ich werde es hier weglassen, aber ich werde die erste Gleichung der obigen Bedingungen verwenden.
In diesem Artikel werden wir dies durch Berechnung überprüfen. Da NumPys gcd ufunc ist, hat es eine äußere Methode, die die Funktion auf den direkten Produktsatz anwendet. Jetzt können Sie sehen, ob die maximale Verpflichtung gleich 1 ist.
>>> np.gcd.outer(mis, mis)
array([[ 37, 1, 1, 1, 1],
[ 1, 73, 1, 1, 1],
[ 1, 1, 109, 1, 1],
[ 1, 1, 1, 145, 1],
[ 1, 1, 1, 1, 181]])
Es wurde bestätigt, dass es 1 ohne die diagonale Komponente war (die diagonale Komponente ist "gcd (x, x)", das Ergebnis ist also "x") [^ 3].
[^ 3]: Wenn Sie eine mechanische Beurteilung vornehmen möchten, können Sie "Kombinationen" von "itertools" verwenden und jede GCD für verschiedene Kombinationen von $ m_i $ $ (m_i, m_j) $ berechnen. ..
Danach kann der chinesische Restsatz normal angewendet werden. Da jedes $ m_i $ elementar zueinander ist, ein kongruentes System
l\equiv a_i \pmod {m_i}
Hat eine einzigartige Lösung $ l $ modulo $ m_0 \ dots m_ {i-1} $. Löse mit crt. Es scheint, dass Sie kein NumPy-Array für das Argument "crt" angeben können. Geben Sie daher das an, das in List zurückgegeben / konvertiert wurde.
>>> l, M = crt(mis.tolist(), a)
>>> l, M
(mpz(2496662055), 7726764205)
Ich habe "l". Dies ist eine multiplizierte ganze Zahl mit "gmpy2".
Beachten Sie, dass M der Wert von $ m_0 \ dots m_ {i-1} $ ist. Ich werde es bestätigen.
>>> np.multiply.reduce(mis)
7726764205
Schließlich erfüllt das berechnete $ l $ $ l \ equiv a_i \ pmod {m_i} $, aber da es auf $ a_i <m_i $ gesetzt ist, ist $ a_i = \ text {rem} ( l, m_i) $ gilt.
Sie haben jetzt $ (l, m) = (2496662055, 36) $, das Ihren Anforderungen entspricht. (Beachten Sie, dass $ \ {m_i \} $ $ [37, 73, 109, 145, 181] $ ist.)
Stellen Sie sicher, dass der Rest der tatsächlichen Division von $ l $ durch jedes $ m_i $ $ a_i $ ist.
Da np.mod ufunc ist, wird es nur durch Angabe eines Arrays oder Skalars berechnet.
>>> decoded = np.mod(l, mis)
>>> decoded
array([mpz(31), mpz(5), mpz(51), mpz(0), mpz(2)], dtype=object)
>>> a_
array([31, 5, 51, 0, 2])
Sie können jetzt bestätigen, dass das Entschlüsselungsergebnis mit dem ursprünglichen "a" übereinstimmt.
Sie können sehen, dass das Entschlüsselungsergebnis in die Klasse "mpz" von "gmpy2" eingeschlossen ist. Sie sollten sich darüber keine Sorgen machen und können es in nachfolgenden Berechnungen als normalen "int" -Wert verwenden. Ich denke, Sie können auch die Trompetenklasse entfernen (unbestätigt).
>>> decoded[1] * 6
mpz(30)
Sie können es so verpacken, als wäre es tatsächlich ein Array, indem Sie eine spezielle Methode in Python implementieren. (Code ist diesmal)
Deshalb habe ich vorgestellt, wie man eine Zahlenfolge durch die β-Funktion ausdrückt. Mit Pythons Unterstützung für Ganzzahlen mit mehreren Längen und mathematische Funktionen sollten Sie in der Lage sein, die Codierung auch für Sequenzen mit realistischer (größerer) Länge zu berechnen. Darüber hinaus ermöglicht die Vektorberechnung von NumPy eine effiziente Berechnung. Die eigentliche Berechnung soll zu einem praktischeren Verständnis der abstrakten Theorie beitragen. wir sehen uns.
Es gibt eine einfachere Möglichkeit zum Codieren. Zum Beispiel, wie es in der ersten Hälfte des Godel-Papiers erscheint
\langle a_0, \dots, a_{n-1}\rangle \mapsto 2^{a_0}\cdot 3^{a_1}\cdot\dots \cdot p_{n-1}^{a_{n-1}}
Es gibt auch eine Methode von. Das Merkmal der β-Funktionsmethode ist, dass die ** Dekodierung nur durch die Restoperation ** durchgeführt werden kann. Dies zeigt, dass Godel den unentscheidbaren logischen Ausdruck, der in der ersten Hälfte des Papiers dargestellt wird, auch als ** mathematischen logischen Ausdruck ** ausdrücken kann (logischer Prädikatausdruck erster Ordnung mit nur $ +, \ cdot, = $). Es war.
Bei Verwendung der β-Funktion kann die Länge der ursprünglichen Sequenz nicht durch Betrachten des codierten Werts bestimmt werden. Godels Beweis musste nicht in der Lage sein, die Länge einer Sequenz zu entschlüsseln, aber wenn Länge benötigt wird
Es kann korrekt verarbeitet werden von.
Ich denke, es gibt verschiedene Methoden.
Es gibt einige, aber hier werde ich die folgende Methode als Methode vorstellen, die alle Einzelaufnahmen aufgibt, aber leicht zu entschlüsseln ist (es gibt eine Möglichkeit, $ -1 $ auf der rechten Seite aufgrund technischer Anforderungen hinzuzufügen). Referenz: https://slideplayer.com/slide/16991262/
(x,y) \mapsto 2^x(2y+1)
$ 2 ^ x $ ist gerade und $ 2y + 1 $ ist ungerade. Daher kann es entschlüsselt werden, indem der codierte Wert so weit wie möglich durch 2 geteilt wird.
Recommended Posts