Godel, Escher, Bach Théorie des nombres typographiques (TNT), puzzles et solutions

Question

Au chapitre 8 de Godel, Escher, Bach de Douglas Hofstader, le lecteur est invité à traduire ces 2 déclarations en TNT:

& "b est une puissance de 2 &";

et

& "b est une puissance de 10 &";

Les réponses suivantes sont-elles correctes?:

(En supposant que '& # 8707;' signifie 'il existe un numéro'):

& # 8707; x: (x.x = b)

i.e. & "; il existe un nombre 'x' tel que x multiplié x est égal à b &";

Si cela est correct, la suivante est tout aussi simple:

& # 8707; x: (x.x.x.x.x.x.x.x.x.x = b)

Je suis confus parce que l'auteur indique qu'ils sont délicats et que le second devrait prendre des heures à résoudre; J'ai dû manquer quelque chose d'évident ici, mais je ne le vois pas!

Answer 1

Vos expressions sont équivalentes aux déclarations & "; b est un nombre carré &"; et " b est la dixième puissance d’un nombre " respectivement. Conversion de & Quot; puissance de & Quot; les déclarations en TNT sont considérablement plus délicates.

Answer 2

En général, je dirais & "b est une puissance de 2 &"; est équivalent à " chaque diviseur de b sauf 1 est un multiple de 2 " ;. C'est-à-dire:

& # 8704; x ((& # 8707; y (y * x = b & amp; & # 172; (x = S0))) & # 8594; < !> # 8707; z (SS0 * z = x))

EDIT: Cela ne fonctionne pas pour 10 (merci pour les commentaires). Mais au moins cela fonctionne pour tous les premiers. Pardon. Je pense que vous devez utiliser une sorte de séquence de codage après tout. Je suggère & Quot; G & # 246; Les théorèmes d’incomplétude de Del & Quot; Raymond Smullyan, si vous voulez une approche plus détaillée et plus générale.

Vous pouvez également coder des séquences de nombres à l'aide du théorème des restes chinois, puis coder des définitions récursives, de manière à pouvoir définir une exponentiation. En fait, c’est essentiellement ainsi que vous pouvez prouver que Peano Arithmetic est achevé.

Essayez ceci:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

Alors

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

devrait indiquer & "; b est la puissance de 10 &"; dire réellement & "; il existe un nombre y et un nombre k tels que y soit le produit de nombres premiers distincts, et la séquence codée par k à travers ces nombres premiers commence par 1, a la propriété que l'élément suivant c de a est 10 * a et se termine par b "

Answer 3

Il existe une solution au " b est une puissance de 10 & "; problème derrière le bouton de spoiler dans le post du scientifique sceptique ici . Cela dépend du théorème du reste chinois issu de la théorie des nombres et de l'existence de séquences arithmétiques de nombres premiers arbitrairement longues. Comme Hofstadter l’a indiqué, il n’est pas facile de trouver des solutions, même si vous connaissez les théorèmes appropriés.

Answer 4

que diriez-vous:

& # 8704; x: & # 8704; y: (SSx & # 8729; y = b & # 8594; & # 8707; z: z & # 8729 ; SS0 = SSx)

(en anglais: tout facteur de b qui est & # 8805; 2 doit lui-même être divisible par 2; littéralement: pour tous les nombres naturels x et y, si (2 + x) * y = b alors cela implique qu'il existe un nombre naturel z tel que z * 2 = (2 + x).)

Je ne suis pas sûr à 100% que cela soit autorisé dans la syntaxe de TNT et calcul propositionnel , cela fait longtemps que je n'ai pas parcouru GEB.

(edit: pour le problème b = 2 ⁿ au moins; je comprends pourquoi le 10 ⁿ serait plus difficile, car 10 n'est pas premier. Mais 11 < sup> n serait la même chose si ce n’est remplacer le seul terme & "; SS0 &" par & "SSSSSSSSSSS0 &";).

Answer 5

En exprimant & "b est une puissance de 10 &", vous n’avez en fait pas besoin du théorème du reste chinois et / ou du codage de séquences finies. Vous pouvez également travailler comme suit (nous utilisons les symboles habituels tels que |, & Gt ;, c-d, comme raccourcis pour les formules / termes ayant une signification évidente):

1. Pour un nombre premier p, notons EXP (p, a) une formule dans TNT disant que & "p est un nombre premier et a est une puissance de p &"; Nous savons déjà comment en construire un. (Pour des raisons techniques, nous ne considérons pas S0 comme une puissance de p, donc ~ EXP (p, S0).)

2. Si p est un nombre premier, nous définissons EXP p (c, a) & # 8790; & # 10216; EXP (p, a) & # 8743; (c-1) | (a-1) & # 10217 ;. Ici, le symbole | est un raccourci pour & "diviser &"; qui peut être facilement défini dans TNT en utilisant un quantificateur et une multiplication existants; il en va de même pour c-1 (a-1, resp.), ce qui signifie & "; le d tel que Sd = c &"; (Sd = a, resp.).
   Si EXP (p, c) est valable (ie c est une puissance de p), la formule EXP _p (c, a) dit que & "A est une puissance de c " depuis un & # 8801; 1 (mod c-1) alors.

3. Ayant une propriété P de nombres (c'est-à-dire des entiers non négatifs), il existe un moyen de se référer, en TNT, au plus petit nombre avec cette propriété: & # 10216; P (a) & # 8743; & # 8704; c: & # 10216; a & Gt; c & # 8594; ~ P (a) & # 10217; & # 10217;.

4. Nous pouvons énoncer la formule exprimant & "; b est une puissance de 10 &"; (pour une meilleure lisibilité, nous omettons les symboles & # 10216; et & # 10217 ;, et nous écrivons 2 et 5 au lieu de SS0 et SSSSS0):
   & # 8707; a: & # 8707; c: & # 8707; d: (EXP (2, a) & # 8743; EXP (5, c) & # 8743; EXP (5, d) & # 8743; d & Gt; b & # 8743; a & # 8901; c = b & # 8743; & # 8704; e: (e > 5 & # 8743; e | c & # 8743; EXP 5 (e, c) & # 8594; ~ EXP 5 (e, d)) & # 8743; & # 8704; e: (& "; e est le plus petit tel que EXP ₅ (c, e) & # 8743; EXP ₅ (d, e) & Quot; & # 8594; (d-2) | (ea))).

Explication: Nous écrivons b = a & # 8901; c = 2 ^x & # 8901; 5 ^y ( x, y > 0) et choisissez d = 5 ^z > b de manière que z et y soient coprimes (par exemple, z peut être un nombre premier). Alors & "Le plus petit e ... &"; est égal à (5 ^z ) ^y = d ^y & # 8801; 2 ^y (mod d-2), et (d-2) | (ea) implique a = 2 ^x = e mod (d-2) = 2 ^y (nous avons 'd-2 > 2 ^y ' et 'd-2 > a' aussi), et donc x = y.

Remarque: Cette approche peut être facilement adaptée pour définir & "; b est une puissance de n &"; pour tout nombre n avec une décomposition fixe a ₁ a ₂ ... a _k , où chacun a _i est une puissance de prime p _i et p _i = p _j & # 8594; i = j.

Answer 6

Voici ce que j'ai proposé:

& # 8704; c: & # 8707; d: < (c * d = b) & # 8594; < (c = SO) v # 8707; e: (d = e * SSO) & Gt; & Gt;

Ce qui se traduit par:

Pour tous les nombres c, il existe un nombre d, tel que si c fois d est égal à b, c est égal à 1 ou il existe un nombre e tel que d est égal à e fois 2.

Ou

Pour tous les nombres c, il existe un nombre d, tel que si b est un facteur de c et d alors c est égal à 1 ou d est un facteur de 2

Ou

Si le produit de deux nombres est b, l’un d’eux est 1 ou l’un d’eux est divisible par 2

Ou

Tous les diviseurs de b sont 1 ou sont divisibles par 2

Ou

b est une puissance de 2

Answer 7

Je pense que la plupart des réponses ci-dessus ont uniquement montré que b devait être un multiple de 4. Que diriez-vous de ceci: & # 8707; b: & # 8704; c: < < & # 8704; e: (c & # 8729; e) = b & amp; ~ & # 8707; c ': & # 8707; c' ':( ssc' & # 8729; ssc '') = c & Gt; & # 8594; c = 2 >

Je ne pense pas que le formatage soit parfait, mais il se lit comme suit:

Il existe b, tel que pour tout c, si c est un facteur de b et que c est premier, alors c est égal à 2.

Answer 8

Voici ce que j'ai proposé pour la déclaration & "b est une puissance de 2 &";

& # 8707; b: & # 8704; a: ~ & # 8707; c: ((a * ss0) + sss0) * c = b

Je pense que cela dit & "; Il existe un nombre b, tel que pour tous les nombres a, il n’existe pas de nombre c tel que (a * 2) + 3 (en d’autres termes, un nombre impair plus grand que 2) multiplié par c, vous donne b. " Donc, si b existe et ne peut pas être égal à zéro et qu’il n’a pas de diviseurs impairs supérieurs à 2, alors b ne serait-il pas nécessairement 1, 2 ou une autre puissance égale à 2?

Answer 9

Pour l'expression ouverte signifiant que b est une puissance de 2, j'ai ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Cela indique effectivement que pour tout a, S (Sa & # 8729; SS0) n'est pas un facteur de b. Mais en termes normaux, S (Sa & # 8729; SS0) est 1 + ((a + 1) * 2) ou 3 + 2a. Nous pouvons maintenant reformuler la déclaration en tant que & "Aucun nombre impair qui est au moins 3 est un facteur de b &"; Ceci est vrai si et seulement si b est une puissance de 2.

Je travaille toujours sur le b est un problème de puissance de 10.

Answer 10

ma solution pour b est une puissance de deux est la suivante: & # 8704; x: & # 8707; y x.y = b (isprime (x) = & Gt; x = SS0)

isprime () ne devrait pas être difficile à écrire.