Puzzle e soluzioni Godel, Escher, Bach Typographical Number Theory (TNT)

https://stackoverflow.com/questions/644569

22-07-2019
|

Domanda

Nel capitolo 8 di Godel, Escher, Bach di Douglas Hofstader, il lettore è sfidato a tradurre queste 2 affermazioni in TNT:

" b è una potenza di 2 "

" b è una potenza di 10 "

Le seguenti risposte sono corrette ?:

(Supponendo '& # 8707;' per indicare 'esiste un numero'):

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

vale a dire. " esiste un numero 'x' tale che x moltiplicato x è uguale a b "

Se è corretto, il prossimo è altrettanto banale:

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

Sono confuso perché l'autore indica che sono difficili e che il secondo dovrebbe richiedere ore per essere risolto; Devo aver perso qualcosa di ovvio qui, ma non riesco a vederlo!

Soluzione

Le tue espressioni sono equivalenti alle istruzioni " b è un numero quadrato " e " b è la decima potenza di un numero " rispettivamente. Conversione di & Quot; potenza di & Quot; le dichiarazioni in TNT sono considerevolmente più complicate.

Altri suggerimenti

In generale, direi " b è una potenza di 2 " è equivalente a " ogni divisore di b tranne 1 è un multiplo di 2 " ;. Cioè:

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

EDIT: questo non funziona per 10 (grazie per i commenti). Ma almeno funziona per tutti i numeri primi. Scusate. Penso che dopo tutto tu debba usare una sorta di sequenza di codifica. Suggerisco & Quot; G & # 246; teorie di incompletezza di del & Quot; di Raymond Smullyan, se si desidera un approccio dettagliato e più generale a questo.

Oppure puoi codificare Sequenze di numeri usando il Teorema del residuo cinese e quindi codificare definizioni ricorsive, in modo da poter definire Esponenziazione. In effetti, questo è fondamentalmente il modo in cui è possibile dimostrare che l'aritmetica di Peano sta diventando completa.

Prova questo:

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

Poi

∃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))))

dovrebbe indicare " b è Potenza di 10 " ;, in realtà dicendo " c'è un numero y e un numero k tali che y è prodotto di numeri primi distinti e la sequenza codificata per k throug questi numeri primi iniziano con 1, hanno la proprietà che il seguente elemento c di a sia 10 * a e termina con b "

C'è una soluzione al " b è una potenza di 10 " problema dietro il pulsante spoiler nel post dello scienziato scettico qui . Dipende dal teorema del resto cinese dalla teoria dei numeri e dall'esistenza di sequenze aritmetiche arbitrariamente lunghe di numeri primi. Come indicato da Hofstadter, non è facile inventarsi, anche se conosci i teoremi appropriati.

che ne dici di:

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

(in inglese: qualsiasi fattore di b che è & # 8805; 2 deve essere divisibile per 2; letteralmente: per tutti i numeri naturali xey, se (2 + x) * y = b allora questo implica che esiste un numero naturale z tale che z * 2 = (2 + x).)

Non sono sicuro al 100% che ciò sia consentito nella sintassi di TNT e calcolo proposizionale , è passato un po 'di tempo da quando ho esaminato GEB.

(modifica: almeno per il problema b = 2 ⁿ; vedo perché il 10 ⁿ sarebbe più difficile poiché 10 non è primo. Ma 11 < sup> n sarebbe la stessa cosa se non la sostituzione del termine " SS0 " con " SSSSSSSSSSS0 " ;.)

Nell'esprimere " b è una potenza di 10 " in realtà non è necessario il teorema del residuo cinese e / o la codifica di sequenze finite. In alternativa puoi lavorare come segue (usiamo i soliti simboli come |, & Gt ;, c-d, come scorciatoie per formule / termini con significato ovvio):

Per un numero primo p, denotiamo EXP (p, a) una formula in TNT che dice che " p è un numero primo e a è una potenza di p " ;. Sappiamo già come costruirne uno. (Per motivi tecnici, non consideriamo S0 un potere di p, quindi ~ EXP (p, S0).)
Se p è un numero primo, definiamo EXP _p (c, a) & # 8790; & # 10216; SCAD (p, a) & # 8743; (C-1) | & (A-1) # 10217 ;. Qui, il simbolo | è una scorciatoia per " divide " che può essere facilmente definito in TNT usando un quantificatore esistenziale e una moltiplicazione; lo stesso vale per c-1 (a-1, resp.) che significa " la d tale che Sd = c " (Sd = a, resp.).
Se EXP (p, c) tiene (ovvero c è una potenza di p), la formula EXP _p (c, a) dice che & Quot; a è una potenza di c " da un & # 8801; 1 (mod c-1) quindi.
Avendo una proprietà P di numeri (cioè numeri interi non negativi), c'è un modo come fare riferimento, in TNT, al numero più piccolo con questa proprietà: & # 10216; P (a) & # 8743; & # 8704; c: & # 10216; a & Gt; c & # 8594; ~ P (a) # 10217 &; # 10217 &;.
Possiamo indicare la formula che esprime " b è una potenza di 10 " (per una migliore leggibilità, omettiamo i simboli & # 10216; e & # 10217 ;, e scriviamo 2 e 5 invece di SS0 e 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 ₅ (e, c) & # 8594; ~ EXP ₅ (e, d)) & # 8743; & # 8704; e: (" e è il più piccolo tale che EXP ₅ (c, e) & # 8743; EXP ₅ (d, e) & Quot; & # 8594; (d-2) | (ea))).

Spiegazione: scriviamo b = a & # 8901; c = 2 ^x & # 8901; 5 ^y ( x, y > 0) e scegli d = 5 ^z > b in modo tale che zey siano coprimi (ad es. z può essere un numero primo). Quindi & Quot; il più piccolo e ... & Quot; è uguale a (5 ^z) ^y = d ^y & # 8801; 2 ^y (mod d-2) e (d-2) | (ea) implica a = 2 ^x = e mod (d-2) = 2 ^y (abbiamo 'd-2 > 2 ^y' e 'd-2 > a', anche), e quindi x = y.

Nota: Questo approccio può essere facilmente adattato per definire " b è una potenza di n " per qualsiasi numero n con una scomposizione fissa a ₁ a ₂ ... a _k, dove ciascuno a _i è una potenza di un primo p _i e p _i = p _j & # 8594; i = j.

Ecco cosa mi è venuto in mente:

# 8704; c: # 8707; d &: & Lt; (c * d = b) # 8594; lt; (c = SO) v <& &! > # 8707; e:!! (d = e * SSO) <> gt; <> gt;

Che si traduce in:

Per tutti i numeri c, esiste un numero d, tale che se c volte d è uguale a b, allora c è 1 o esiste un numero e tale che d è uguale a e volte 2.

Per tutti i numeri c, esiste un numero d, tale che se b è un fattore di c e d allora c è 1 o d è un fattore di 2

Se il prodotto di due numeri è b, uno di questi è 1 o uno di essi è divisibile per 2

Tutti i divisori di b sono 1 o sono divisibili per 2

b è una potenza di 2

Penso che la maggior parte di quanto sopra abbia dimostrato che b deve essere un multiplo di 4. Che ne dici di questo: & # 8707; b: & # 8704; c: < < & # 8704; e: (c & # 8729; e) = b & amp; ~ & # 8707; c ': & # 8707; c' ':( ssc' & # 8729; ssc '') = c & Gt; & # 8594; c = 2 >

Non penso che la formattazione sia perfetta, ma si legge:

Esiste b, tale che per tutti c, se c è un fattore b e c è primo, quindi c uguale a 2.

Ecco cosa mi è venuto in mente per l'affermazione " b è una potenza di 2 "

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

Penso che questo dica " Esiste un numero b, tale che per tutti i numeri a, non esiste un numero c tale che (a * 2) + 3 (in altre parole, un numero dispari maggiore di 2) moltiplicato per c, ti dà b. " Quindi, se b esiste e non può essere zero e non ha divisori dispari maggiori di 2, allora b non sarebbe necessariamente 1, 2 o un altro potere di 2?

Per l'espressione aperta che significa che b è una potenza di 2, ho ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Questo dice effettivamente che per tutti a, S (Sa & # 8729; SS0) non è un fattore di b. Ma in termini normali, S (Sa & # 8729; SS0) è 1 + ((a + 1) * 2) o 3 + 2a. Ora possiamo riformulare l'istruzione come & Quot; nessun numero dispari che sia almeno 3 è un fattore di b & Quot ;. Questo è vero se e solo se b è una potenza di 2.

Sto ancora lavorando sul problema b è un potere di 10.

la mia soluzione per b è una potenza di due è: & # 8704; x: & # 8707; y x.y = b (isprime (x) = & Gt; x = SS0)

isprime () non dovrebbe essere difficile da scrivere.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow