Post by Olivier MiakinenPost by Samuel DEVULDERSavez vous ce à quoi cela correspond ?
Çn erffrzoyr à ha cebtenzzr ra SENPGENA
Ça ressemble à un programme en FRACTRAN.
En effet cette suite de fractions [17/91, 78/85, 19/51, 23/38, 29/33,
77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1] est un
programme pour la machine dite FRACTRAN (un truc qui fait penser à
FORTRAN, mais à base de FRACtion au lieu de FORmules) et qui a été
inventé par Conway vers la fin des années 80 (en plein pendant mon
époque "mandelbrot".)
https://link.springer.com/chapter/10.1007/978-1-4612-4808-8_2
En francais: https://fr.wikipedia.org/wiki/FRACTRAN
Un programme FRACTRAN s'interprète très simplement. On présente un
entier N à la machine, qui le multiplie alors par toutes les fractions
dans l'ordre. La 1ère multiplication qui donne un entier N' est alors
représentée à la machine qui repart pour un tour. Si aucun des produit
n'est entier alors la machine s'arrête.
C'est vraiment très simple et une implémentation dans d'autres langages
se code en quelques lignes sans aucun soucis.
Le truc fort dans l'histoire est que la suite de fractions écrite plus
haut produit, avec cette machine et le nombre 2 en entrée des tas de
nombres, mais ceux qui sont de la forme 2^p, sont dans l'ordre 2^2, 2^3,
2^5, 2^7, 2^11, 2^13, 2^17, .. bref la machine "énumère" (en un sens)
tous les nombres premiers dans l'ordre sans en manquer un seul!!!
Vous ne me croyez pas ? Sisi j'en vois qui doutent.. Et bien codez cela
dans le langage de votre choix et vous verrez que ca marche!
Comment c'est possible ? Et bien les machines FRACTRAN (et leur langage
associé) est Turing-complet. On peut calculer tout ce qui est calculable
avec elles comme les nombres premiers, les décimales de PI ou que
sais-je encore.
TIP: essayez de présenter 2^0, puis 2^1, puis 2^2 puis 2^3 puis 2^4 et
repérer la première sortie du type 2^d qui apparait au programme
suivant: [365/46, 29/161, 79/575, 679/451, 3159/413, 83/407, 473/371,
638/355, 434/335, 89/235, 17/209, 79/122, 31/183, 41/115, 517/189,
111/83, 305/79, 23/73, 73/71, 61/67, 37/61, 19/59, 89/57, 41/53, 833/47,
53/43, 86/41, 13/38, 23/37, 67/31, 71/29, 83/19, 475/17, 59/13, 41/291,
1/7, 1/11, 1/1024, 1/97, 89/1]
C'est magique, n'est-ce pas !!!
Post by Olivier MiakinenPost by Samuel DEVULDERDhnaq w'nv eényvfé dh'ha rafrzoyr qr senpgvbaf cbhinvg êger vagreceégé pbzzr har ynatntr ghevat-pbzcyrg, pn z'n snvg ienvzrag ovmneer. Nhgnag w'nv snvg qrf gehpf éfbgéevdhr ghevat-pbzcyrg pbzzr oenva-shpx (uggcf://se.jvxvcrqvn.bet/jvxv/Oenvashpx) dhr yà wr ar z'l nggraqnvf cnf, fhegbhg nirp fv crh qr senpgvbaf.
W'nv qh pbqre har znpuvar SENPGENA zbv zêzr cbhe iéevsvre dhr pryn pnyphynvg rssrpgvirzrag yrf abzoerf cerzvref cnepr dhr wr iblnvf cnf qh gbhg pbzzrag pryn égnvg cbffvoyr. Ra bcgvzvfnag yr pbqr cbhe hgvyvfre har qépbzcbfvgvba ra snpgrhef cerzvref (pne fvaba ba n qrf 2^a dhv qécnffrag 32ovgf geèf ivgr) p'rfg qrirah geèf pynve: p'rfg whfgr har znpuvar ZVFC (zvavzny vafgehpgvba frg) nirp cyrva qr ertvfgerf, yrfdhryf fbag "rapbqéf" cne yrf abzoerf cerzvref. P'rfg éivqrag, znvf zbvaf zntvdhr.
sam (en clair lundi)
Quand j'ai réalisé qu'un ensemble de fractions pouvait être interprété
comme une langage turing-complet, ca m'a fait vraiment bizarre. Autant
j'ai fait des trucs ésotérique turing-complet comme brain-fuck
(https://fr.wikipedia.org/wiki/Brainfuck) que là je ne m'y attendais
pas, surtout avec si peu de fractions.
J'ai du coder une machine FRACTRAN moi même pour vérifier que cela
calculait effectivement les nombres premiers parce que je voyais pas du
tout comment cela était possible. En optimisant le code pour utiliser
une décomposition en facteurs premiers (car sinon on a des 2^n qui
dépassent 32bits très vite) c'est devenu très clair: c'est juste une
machine MISP (minimal instruction set) avec plein de registres, lesquels
sont "encodés" par les nombres premiers. C'est évident, mais moins magique.
Oui alors quand on comprends "le truc", c'est moins magique, mais ca
n'en reste pas moins très beau, et très amusant à programmer surtout si
on fait ca sur 8bits et on ajoute des extensions permettant de faire des
entrées sorties simplifiées (par exemple: la machine affiche p en
décimal si le nombre représenté à l'entrée est du type 2^p).
Mathématiquement ce langage est à la fois très compact et très puissant.
Ainsi Conway a produit le programme suivant: [583/559, 629/551, 437/527,
82/517, 615/329, 371/129, 1/115, 53/86, 43/53, 23/47, 341/46, 41/43,
47/41, 29/37, 37/31, 37/31, 299/29, 47/23, 161/15, 527/19, 159/7, 1/17,
1/13, 1/3] qui est tel que pour toute fonction partielle récursive (f)
il existe un entier c_f tel que si on présente c_f*2^2^n à la machine,
elle finir par produire la puissance de 2 exacte 2^2^f(c).
Bim! *mindblowing*
Wouhaaa la puissance du truc mec! Je plane! Et tout ca avec des
programmes tout petits qui ne demandent pas des zillions de lignes de
codes de dépendances, de machin et bidules pour fonctionner. C'est beau
l'informatique théorique moi je trouve :)
==> Merci Conway!
sam.