Calculons la fonction β (fonction β de Gedell) avec SymPy. À ce moment-là, essayez de réduire le nombre de Godel dans le résultat autant que possible.
De plus, puisque cet article sert également de pratique pour le tableau NumPy de l'auteur, il y a des endroits où des calculs vectoriels à la mode sont exécutés de force.
--Shin Hayashi, Mitsuko Yasugi Traduit et explique le "Théorème d'Incomplétude de Gedell" Iwanami Bunko (Bleu 944-1), 2006.
Une fonction utilisée pour le décodage lors de l'encodage d'une chaîne de nombres naturels en un nombre naturel. Il est appelé parce qu'il apparaît dans la preuve du Théorème d'Incomplétude de Godel (1931).
Supposons ce qui suit:
Pour un entier naturel $ l, m, i $ ($ m> 0,0 \ le i \ le n-1 $) la fonction $ \ beta $
\beta(l,m,i) = \text{rem}(l,(i+1)m + 1)
Défini dans (rem est une opération de reste normale, généralement mod ou% est utilisé) [^ 1].
[^ 1]: $ im + 1 $ est positif, donc rem peut être calculé normalement.
A ce moment, pour une suite de nombres naturels concrètement donnée $ a = \ langle a_0, \ dots, a_ {n-1} \ rangle $ de longueur $ n \ ge 1 $, un certain nombre naturel $ l, m Vous pouvez calculer $ de telle sorte que pour $ 0 \ le i \ le n-1 $, $ \ beta (l, m, i) = a_i $ [^ 2]. Autrement dit, $ (l, m) $ peut être considéré comme la représentation naturelle de la séquence (c'est-à-dire le ** nombre de Godel **). Il existe également un moyen de coder une paire de nombres naturels avec un seul nombre naturel (voir supplément), ce qui entraîne le codage de la séquence de nombres naturels sous forme de nombre naturel. Dans la discussion qui suit, nous allons procéder sans spécifier l'encodage / décodage de la paire.
[^ 2]: Je ne dis rien sur $ i $ plus grand que ça.
Puisque le théorème du reste chinois (CRT) est nécessaire pour calculer $ l $, nous utiliserons SymPy, une bibliothèque Python avec la fonction crt.
Puisque nous avons besoin d'un exemple concret, considérons un exemple de codage d'un tableau de longueur 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
C'est pratique, alors convertissons-le en tableau NumPy ʻa_. Créez également un tableau d'indices pour ʻa_.
>>> a_ = np.array(a)
>>> a_
array([31, 5, 51, 0, 2])
>>> a_idx = np.arange(n)
>>> a_idx
array([0, 1, 2, 3, 4])
Après avoir donné une politique sur le calcul pour l'encodage, calculons en fait avec Python. Étant donné une séquence de nombres comme ci-dessus, la politique de codage est la suivante:
--Calculer $ m $ d'une manière ou d'une autre pour que chaque $ m_i $ soit mutuellement exclusif (+ satisfaisant à certaines conditions). --Calculer $ l $ avec le théorème chinois du reste, en utilisant le fait que chaque $ m_i $ est premier l'un par rapport à l'autre.
En général, le plancher est utilisé pour calculer $ m $. Cependant, cette méthode rend $ m $ très grand. Alors $ l $ a tendance à être grand. Dans cet article, j'essaierai de calculer en faisant $ m $ et éventuellement $ l $ aussi petits que possible. Cependant, je ne suis pas sûr que ce soit le minimum.
Ci-après, il est exprimé par $ m_i = (i + 1) m + 1 $. Autrement dit, la définition de la fonction β est $ \ beta (l, m, i) = \ text {rem} (l, m_i) $.
mL'article de Wikipédia "Numérotation de Gödel pour les séquences" est un peu déroutant, mais il explique les conditions les plus faibles possibles que $ m $ devrait remplir et est utile (je ne sais pas si c'est la plus faible ou non). Selon lui, si $ m $ remplit les conditions suivantes, il peut être adopté pour un encodage correct.
i\mid m \quad (1\le i\le n-1) \\
a_i < m_i \quad (0\le i \le n-1)
La première équation signifie que $ m $ est un multiple commun de ** $ 1, \ dots, n-1 $ **. Par conséquent, il est recommandé de lister les ** multiples communs minimaux (LCM) $ m_0 $ multiples ** de $ 1, \ points, n-1 $ comme candidats pour $ m $, et de trouver le plus petit qui satisfait la deuxième équation. Probablement. Essayons.
m0NumPy a une fonction à deux arguments lcm. Puisqu'il s'agit du soi-disant ufunc, vous pouvez calculer le LCM pour un tableau en utilisant la méthode reduction. J'essaierai. Puisque nous avons créé le tableau d'indices $ [0,1, \ dots, n-1] $ plus tôt, nous utiliserons $ [1, \ dots, n-1] $ comme tranche.
>>> m0 = np.lcm.reduce(a_idx[1:])
>>> m0
12
Un calcul manuel du LCM de 1,2,3,4 $ est certainement de 12 $. Ce multiple $ m $ de $ m_0 $ satisfait toujours la première équation.
Dans la section suivante, nous calculerons $ \ {m_i \} $ pour divers $ m $. Ici, nous allons vous expliquer comment le faire en premier.
Pour chaque $ m $, vous devez trouver $ \ {m_i \} $ et le comparer à $ \ {a_i \} $.
Ce premier est $ \ {m_i \ mid 0 \ le i \ le n-1 \} = \ {(i + 1) m + 1 \ mid 0 \ le i \ le n-1 \} $ .. Puisque la plage de $ i $ correspond à ʻa_idxdéfinie précédemment, elle peut être calculée à la fois par un calcul de tableau. Définissez la fonction souhaitée commem_i_seq`.
>>> def m_i_seq(m): return (a_idx + 1) * m + 1
Si vous essayez de calculer pour m = 12, ce sera comme ça.
>>> mis = m_i_seq(12)
>>> mis
array([13, 25, 37, 49, 61])
(Mis est une image de $ m_i $ s)
Trouvons maintenant $ m $ (un multiple de $ m_0 $) qui satisfait la deuxième équation de la condition. Premièrement, $ \ {m_i \} $ pour le cas de $ m = m_0 = 12 $ est mis = [13 25 37 49 61] comme calculé précédemment. La comparaison entre ceci et $ \ {a_i \} $ peut également être calculée à la fois avec la fonction de calcul vectoriel du tableau NumPy.
>>> a_ < mis
array([False, True, False, True, True])
Vous pouvez voir que cela ne vaut pas pour les deux $ i $.
Ensuite, doublons $ m_0 $ et fixons $ m = 24 $. En ce moment,
>>> mis = m_i_seq(24)
>>> mis
array([ 25, 49, 73, 97, 121])
>>> a_ < mis
array([False, True, True, True, True])
Cela n'a pas encore été établi. C'est ce qui se passe lorsque $ m = 36 $.
>>> mis
array([ 37, 73, 109, 145, 181])
>>> a_ < mis
array([ True, True, True, True, True])
Tout va bien parce que tout est "vrai". Adoptez ce $ m = 36 $.
En déterminant $ m $ comme décrit ci-dessus, nous pouvons prouver que les deux éléments différents de $ \ {m_i \} $ sont élémentaires l'un par rapport à l'autre. Je vais l'omettre ici, mais j'utiliserai la première équation des conditions ci-dessus.
Dans cet article, nous allons vérifier cela par calcul. Puisque gcd de NumPy est ufunc, il a une méthode ʻouter` qui applique la fonction à l'ensemble de produits direct. Vous pouvez maintenant voir si l'engagement maximum est égal à 1.
>>> 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]])
Il a été confirmé qu'il était de 1 en excluant la composante diagonale (la composante diagonale est «gcd (x, x)», donc le résultat est «x») [^ 3].
[^ 3]: Si vous voulez faire un jugement mécanique, vous pouvez utiliser des «combinaisons» de «itertools» et calculer chaque GCD pour différentes combinaisons de $ m_i $ $ (m_i, m_j) $. ..
Après cela, le théorème du reste chinois peut être appliqué normalement. Puisque chaque $ m_i $ est élémentaire l'un par rapport à l'autre, un système congruent
l\equiv a_i \pmod {m_i}
A une solution unique $ l $ modulo $ m_0 \ dots m_ {i-1} $. Résolvez en utilisant crt. Il semble que vous ne puissiez pas spécifier un tableau NumPy pour l'argument de crt, alors spécifiez celui retourné / converti en List.
>>> l, M = crt(mis.tolist(), a)
>>> l, M
(mpz(2496662055), 7726764205)
J'ai «l». Il s'agit d'un entier multiplié par "gmpy2".
Notez que «M» est la valeur de $ m_0 \ dots m_ {i-1} $. Je vais le confirmer.
>>> np.multiply.reduce(mis)
7726764205
Enfin, le $ l $ calculé satisfait $ l \ equiv a_i \ pmod {m_i} $, mais comme il est mis à $ a_i <m_i $, $ a_i = \ text {rem} ( l, m_i) $ tient.
Vous avez maintenant $ (l, m) = (2496662055, 36) $ qui répond à vos besoins. (Notez que $ \ {m_i \} $ est $ [37, 73, 109, 145, 181] $.)
Assurez-vous que le reste de la division réelle de $ l $ par chaque $ m_i $ est $ a_i $.
Puisque np.mod est ufunc, il le calculera simplement en spécifiant un tableau ou un scalaire.
>>> 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])
Vous pouvez maintenant confirmer que le résultat du déchiffrement correspond à l'original «a».
Vous pouvez voir que le résultat du déchiffrement est enveloppé dans la classe mpz de gmpy2. Cela ne devrait pas être un problème et pourrait être utilisé dans les calculs ultérieurs comme une valeur «int» normale. Je pense que vous pouvez également supprimer la classe trompette (non confirmée).
>>> decoded[1] * 6
mpz(30)
Vous pouvez l'empaqueter comme s'il s'agissait en fait d'un tableau en implémentant une méthode spéciale en Python. (Le code est cette fois)
C'est pourquoi j'ai présenté comment exprimer une séquence de nombres par la fonction β. Avec la prise en charge par Python de plusieurs entiers de longueur et de fonctions mathématiques, vous devriez être en mesure de calculer le codage même pour des séquences de longueur réalistes (plus grandes). De plus, le calcul vectoriel de NumPy permet un calcul efficace. Le calcul proprement dit devrait aider à une compréhension plus pratique de la théorie abstraite. à plus.
Il existe un moyen plus simple d'encoder. Par exemple, tel qu'il apparaît dans la première moitié de l'article de Godel
\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}}
Il existe également une méthode de. La caractéristique de la méthode de la fonction β est que ** le décodage ne peut être effectué que par l'opération de reste **. Cela montre que Godel peut également exprimer l'expression logique indécidable présentée dans la première moitié de l'article comme ** expression logique mathématique ** (expression logique de prédicat du premier ordre avec seulement $ +, \ cdot, = $). C'était.
Lors de l'utilisation de la fonction β, la longueur de la séquence d'origine ne peut pas être déterminée en regardant la valeur codée. La preuve de Godel n'avait pas besoin de pouvoir décrypter la longueur d'une séquence, mais si la longueur est nécessaire
Il peut être traité correctement par.
Je pense qu'il existe différentes méthodes.
Il y en a quelques-uns, mais ici, je vais présenter la méthode suivante comme une méthode qui abandonne tous les plans uniques mais qui est facile à déchiffrer (il existe un moyen d'ajouter $ -1 $ sur le côté droit en raison des exigences techniques). Référence: https://slideplayer.com/slide/16991262/
(x,y) \mapsto 2^x(2y+1)
$ 2 ^ x $ est pair et $ 2y + 1 $ est impair. Par conséquent, il peut être déchiffré en divisant la valeur codée par 2 autant que possible.
Recommended Posts