Godel Escher Bach

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Qualcuno ha letto il libro \"Godel, Escher, Bach: un\'eterna girlanda brillante\" di Douglas Hofstadter? Se si forse vi ricorderete che a pag 235, quanto parla dell\'aritmetica tipografica, propone per esercitarsi di formalizzare nel linguaggio li descritto diverse proposizioni, dicendo inoltre che \"b è una potenza di 2 potrebbe sembrare un po\' più difficile delle altre ma non è niente in confronto a b è una potenza di 10\" sconsigliando inoltre di cimentersi nell\'ultima. Io l\'ho fatto e devo ammettere che se \"b è una potenza di 2\" (o di qualsiasi altro primo) non mi ha causato particolari difficoltà \"b è una potenza di 10\" mi blocca... riesco a formalizzare b=2^n*5^m, ma non mi viene in mente come fare a dire che n=m... qualcuno di voi ci è riuscito? Se si potrebbe postare la risposta? Grazie!

Messaggio da **ma_go** » 01 gen 1970, 01:33

se devo essere sincero mi sono perso il testo del problema...
 non è che lo puoi trascrivere, visto che il libro manca ancora nella mia piccola biblioteca scientifica?
 grazie...

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Ehm... a dire la verità è un po\' lungo da fare dato che dovrei descrivere tutto l\'alfabeto di quel linguaggio, ma proverò a riassumere: usando solo i quantificatori logici \"non\" \"e\" \"vel\" \"implica\" \"esiste\" \"per ogni\" i simboli di addizione (+) e di moltiplicazione (*) il simbolo di uguaglianza (=), tutte le variabili necessarie, il simbolo \"tale che\" e ogni numero naturale. Inoltre ogni variabile indica necessariamente un numero naturale e di fatto si può usare anche il simbolo maggiore (>) liberamente dato che è facile scriverlo a partire dagli altri (a>b diventa \"esiste un c tale che a=b+c). Il problema è, usando solo quest\'alfabeto, scrivere la proposizione \"b è una potenza di 10\". Come esercizio, per impratichirvi scriverete prima \"b è una potenza di 2\".
 per ma_go se non ci riesci non preoccuparti, è colpa mia che mi sono spiegato male...

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

Carino!
 Credo di esserci riuscito. Purtroppo la dimostrazione è lunga, e tra qualche ora ho un esame... Spero di non dimenticarmela, nel frattempo!

DD · Messaggio da DD » 01 gen 1970, 01:33

che io sappia si può fare o col teorema cinese del resto, oppure spiegando come viene scritta una potenza di 10 in una certa base p con p primo bello grosso
 (oppure, modo più semplice ma non onesto, usando il simpatico risultato di Goedel secondo cui nella logica del primo ordine + assiomi dell\'aritmetica si possono esprimere tutte le funzioni primitive ricorsive, e quindi anche exp(a,b)=a^b)

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

Già, già. Bel bordello. Anche io uso il Teorema Cinese del Resto, per codificare \"successioni\" di potenze in un solo intero. Quella che segue è la trascrizione di tutto il procedimento, nella stesura della quale mi sono avvalso della collaborazione di un certo Alessio Martini. Nelle prime righe ho messo delle definizioni ausiliarie, al solo scopo di fare un po\' di ordine e di non dover riscrivere troppe volte le stesse cose. Ah, la dimostrazione che tutto \'sto macello funziona è lasciata per esercizio al lettore segaiolo mentale, oppure è lasciata a me quando avrò più voglia di adesso. Buon divertimento.
 
 
 // x è minore o uguale a y
 x<=y := esiste z tale che y=x+z
 
 // x è minore di y
 x<y := x<=y e non x=y
 
 // x divide y
 x|y := esiste z tale che y=x*z
 
 // x è libero da quadrati
 x ldq := per ogni y, ((y*y)|x implica y=1)
 
 // x è un numero primo
 x primo := (per ogni y, (y|x implica (y=1 vel y=x))) e non x=1
 
 // x è il più piccolo numero primo che divide y
 x mpd y := x primo e x|y e per ogni z, ((z primo e z|y) implica x<=z)
 
 // x è il più grande numero primo che divide y
 x Mpd y := x primo e x|y e per ogni z, ((z primo e z|y) implica z<=x)
 
 // x e y sono divisori primi consecutivi di z
 (x,y) dpc z := x primo e y primo e x<y e (x*y)|z e per ogni w, ((w primo e x<w e w<y) implica non w|z)
 
 // x e y sono congrui modulo z
 x==y (mod z) := (esiste w tale che y=x+w*z) vel (esiste w tale che x=y+w*z)
 
 // nella \"successione\" codificata s, al numero (primo) n è associato il valore di x
 x cod (s,n) := 0<=x e x<n e x==s (mod n)
 
 // x è il primo valore nella \"successione\" s, codificata rispetto al modulo m
 x first (s,m) := esiste z tale che ((z mpd m) e (x cod (s,z)))
 
 // x è l\'ultimo valore nella \"successione\" s, codificata rispetto al modulo m
 x last (s,m) := esiste z tale che ((z Mpd m) e (x cod (s,z)))
 
 // nella \"successione\" s, ai numeri (primi) b ed a sono associati due valori il cui rapporto è q
 (a,b) progr (s,q) := per ogni x, per ogni y, ((x cod (s,a) e y cod (s,b)) implica y=x*q)
 
 // x è una potenza di y
 x power y := esiste m tale che esiste s tale che ((m ldq) e (1 first (s,m)) e (x last (s,m)) e per ogni a, per ogni b, ((a,b) dpc m implica (a,b) progr (s,y)))
 
 
 (notare che, per dire \"x è una potenza di p\", con p primo, bastava dire \"per ogni b, (b|a implica p|b)\", hehehe!)[addsig]