FRACTRAN

FRACTRAN

FRACTRAN este un limbaj de programare exotic și complet Turing aplicabil întregilor naturali . A fost inventat de matematicianul John Conway, care a publicat o descriere a acestuia în 1987.

Constă în reprezentarea oricărei funcții calculabile pe numere întregi printr-o listă de fracții .

Pentru a găsi imaginea unui număr întreg A, căutăm în listă prima dintre fracțiile care înmulțite cu A dă un număr întreg B, apoi aplicăm procedura din nou întregului B. Dacă niciuna dintre fracțiile listei înmulțite cu rezultatul precedent nu dă un număr întreg, procedura se oprește.

Exemplu

Luați în considerare programul FRACTRAN corespunzător listei de fracții . (310,43){\ displaystyle \ left ({\ frac {3} {10}}, {\ frac {4} {3}} \ right)}

Dacă este aplicat întregului 14, nici ca și nici nu sunt întregi, programul se oprește imediat. 310×14{\ displaystyle {\ frac {3} {10}} \ times 14}43×14{\ displaystyle {\ frac {4} {3}} \ times 14}

Dacă îl aplicăm întregului 15, obținem succesiv 20 (pentru că numai unul este un număr întreg), apoi 6 (pentru că este un număr întreg), apoi 8 (pentru că doar unul dă un număr întreg), atunci procedura se oprește. 43×15{\ displaystyle {\ frac {4} {3}} \ times 15}310×20{\ displaystyle {\ frac {3} {10}} \ times 20}43×6{\ displaystyle {\ frac {4} {3}} \ ori 6}

Principiu

Principiul se bazează pe existența unei descompuneri în produse a factorilor primi ai numerelor întregi și pe noțiunea de evaluare p-adică .

Fiecare număr întreg A are o descompunere unică a factorului prim în care exponentul numărului prim p se numește evaluarea lui p în A și se notează . vp(LA){\ displaystyle v_ {p} (A)}

Pentru un număr întreg A dat, toate sunt zero, cu excepția unui număr finit din ele. Înmulțirea numărului întreg A cu o fracție care permite obținerea unui număr întreg B, constă în operarea adunărilor și scăderilor pe . vp(LA){\ displaystyle v_ {p} (A)}vp{\ displaystyle v_ {p}}

Astfel, lista precedentă funcționează pe evaluările de 2, 3 și 5. Prima fracție elimină 1 din evaluările de 2 și 5 (dacă este posibil) și crește cu 1 valoarea de 3, a doua fracție acționează numai atunci când evaluarea de 2 sau 5 este zero, crește evaluarea de 2 cu două unități și scade cea de 3 cu o unitate.

Când A este scris cu A 'prim cu 30 și , folosind două bucle, procedura transformă A în apoi în și apoi se oprește. 2la×3b×5vs.×LA′{\ displaystyle 2 ^ {a} \ times 3 ^ {b} \ times 5 ^ {c} \ times A '}vs.≤la{\ displaystyle c \ leq a}B=2la-vs.×3b+vs.×LA′{\ displaystyle B = 2 ^ {ac} \ times 3 ^ {b + c} \ times A '}2la+2b+vs.×LA′{\ displaystyle 2 ^ {a + 2b + c} \ times A '}

Programul face astfel posibilă definirea operațiunilor asupra evaluărilor.

Operațiuni de bază

Plus

Lista care conține fracția unică face posibilă sumarea evaluărilor de 2 și 3: când A este scris cu A 'prim cu 6, procedura se aplică până când A este transformat în . 32{\ displaystyle {\ frac {3} {2}}}2la×3b×LA′{\ displaystyle 2 ^ {a} \ times 3 ^ {b} \ times A '}3la+b×LA′{\ displaystyle 3 ^ {a + b} \ times A '}

Multiplicare

Putem crea o funcție multiplicativă folosind o buclă aditivă. Pentru aceasta, este necesar să se introducă noțiunea de stare în algoritm. Acest algoritm se aplică unui număr și îl transformă în și funcționează la evaluările de 2, 3, 5, dar și 7, 11 și 13: 2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}5lab{\ displaystyle 5 ^ {ab}}

Starea curenta	Condiție	Acțiune	Următoarea stare
LA	v7> 0	Scădeți de la 1 la v7 adăugați 1 la v3	LA
	v7 = 0 și v2> 0	Scădeți 1 din v2	B
	v7 = 0 și v2 = 0 și v3> 0	Scădeți 1 din v3	LA
	v7 = 0 și v2 = 0 și v3 = 0	Stop
B	v3> 0	Scădeți 1 din v3 Adăugați 1 în v5 Adăugați 1 în v7	B
	v3 = 0	Nimic	LA

Starea B este o buclă care adaugă v3 la v5 și, de asemenea, mută v3 la v7, iar starea A este o buclă care repetă bucla B v2 de ori. Starea A returnează, de asemenea, la v3 valoarea inițială (prezentă în v7) când bucla B este terminată.

Pentru a gestiona aceste stări, sunt necesare noi variabile: ele joacă rolul de indicatori de stare. Semnalizatoarele de stare pentru bucla B sunt v11 și v13. Sunt necesari doi indicatori de stare pentru bucla unică B: într-adevăr, primul indicator (v11) fiind consumat la intrarea buclei, este necesar să aveți un al doilea indicator (v13) pentru a indica programului că trebuie să continue în aceeași stare. Semnalizatorul v13 este comutat la v11 în timpul instrucțiunii „următoare” a buclei.

Prin adăugarea indicatorilor de stare și a instrucțiunilor în tabelul algoritmului de multiplicare, obținem:

instructiune fractran	Starea curenta	Indicatori de stare	Condiție	Acțiune	Următoarea stare
37{\ displaystyle {\ frac {3} {7}}}	LA	Nu	v7> 0	Scădeți 1 din v7 Adăugați 1 din v3	LA
112{\ displaystyle {\ frac {11} {2}}}			v7 = 0 și v2> 0	Scade 1 din v2 Setați v11 la 1	B
13{\ displaystyle {\ frac {1} {3}}}			v7 = 0 și v2 = 0 și v3> 0	Scădeți 1 din v3	LA
			v7 = 0 și v2 = 0 și v3 = 0	Stop
5⋅7⋅133⋅11,1113{\ displaystyle {\ frac {5 \ cdot 7 \ cdot 13} {3 \ cdot 11}}, {\ frac {11} {13}}}	B	v11, v13	v3> 0	Scădeți 1 din v3 Adăugați 1 în v5 Adăugați 1 în v7	B
111{\ displaystyle {\ frac {1} {11}}}			v3 = 0	Setați v11 la 0	LA

Atunci când scriem lista instrucțiunilor FRACTRAN, trebuie să punem ultimele instrucțiuni ale stării A, deoarece starea A nu are indicator de stare, este starea implicită.

Astfel, programul de multiplicare FRACTRAN este următoarea listă:

(45533,1113,111,37,112,13){\ displaystyle \ left ({\ frac {455} {33}}, {\ frac {11} {13}}, {\ frac {1} {11}}, {\ frac {3} {7}}, {\ frac {11} {2}}, {\ frac {1} {3}} \ right)}

Dacă introduceți numărul , programul revine . 2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}5lab{\ displaystyle 5 ^ {ab}}

Substracție

Fracția simplă transformă numărul în 16{\ displaystyle {\ frac {1} {6}}}2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}

• 2la-b30{\ displaystyle 2 ^ {ab} 3 ^ {0}}, dacă  ;la>b{\ displaystyle a> b}
• 203b-la{\ displaystyle 2 ^ {0} 3 ^ {ba}}, dacă  ;b>la{\ displaystyle b> a}
• 2030{\ displaystyle 2 ^ {0} 3 ^ {0}}da .la=b{\ displaystyle a = b}

Diviziunea euclidiană

Diviziunea euclidiană a unui prin b ( a și b numere naturale, b > 1) este dat de două naturale numere q și r astfel încât r < b și a = bq + r . Această divizare euclidiană poate fi văzută ca o buclă de scăderi: împărțirea a lui b este de a scădea b dintr - o cât de multe ori este necesar, numărul de ori această scădere se efectuează corespunde q , ultima valoare într - o potrivește cu restul.

Algoritmul funcționează apoi pe v2 conținând a , v3 conținând b , v5 destinat să conțină q și v7 destinat să conțină r . Aceste variabile sunt completate de 4 indicatori de stare v11, v13, v17, v19.

Programul FRACTRAN care urmează este format din trei stări:

• starea A funcționează diferit în funcție de faptul dacă v3 este mai mic sau mai mare decât v2;
  • dacă v3 ≤ v2, bucla scade v3 din v2, golește v3 în v7, adaugă 1 la v5 și merge la starea B;
  • dacă v3> v2, bucla v2 se golește în v7 și trece la starea X.
• starea B este o supra-buclă care re-execută bucla A după ce a golit anterior v7 în v3;
• starea X constă în golirea v3 când v2 este gol și v3 este ne-gol.

Instrucțiuni FRACTRAN	Starea curenta	Indicatori de stare	termeni si conditii	Acțiuni	Următoarea stare
7⋅132⋅3⋅11,1113{\ displaystyle {\ frac {7 \ cdot 13} {2 \ cdot 3 \ cdot 11}}, {\ frac {11} {13}}}	LA	v11, v13	v2> 0 și v3> 0	Scade 1 din v2 Scade 1 din v3 Adăugați 1 din v7	LA
13⋅11{\ displaystyle {\ frac {1} {3 \ cdot 11}}}			v2 = 0 și v3> 0	Scade 1 din v3 Setați v11 la 0	X
5⋅1711{\ displaystyle {\ frac {5 \ cdot 17} {11}}}			v3 = 0	Adăugați 1 la v5 Setați v11 la 0 Setați v17 la 1	B
3⋅197⋅17,1719{\ displaystyle {\ frac {3 \ cdot 19} {7 \ cdot 17}}, {\ frac {17} {19}}}	B	v17, v19	v7> 0	Scădeți 1 din v7 Adăugați 1 din v3	B
1117{\ displaystyle {\ frac {11} {17}}}			v7 = 0	Setați v11 la 1 Setați v17 la 0	LA
13{\ displaystyle {\ frac {1} {3}}}	X		v3> 0	Scădeți 1 din v3	X
			v3 = 0	Stop

Scrierea programului este apoi:

(9166,1113,133,8511,57119,1719,1117,13){\ displaystyle \ left ({\ frac {91} {66}}, {\ frac {11} {13}}, {\ frac {1} {33}}, {\ frac {85} {11}}, {\ frac {57} {119}}, {\ frac {17} {19}}, {\ frac {11} {17}}, {\ frac {1} {3}} \ right)}

Trebuie doar trebuie să introduceți pentru a ajunge la ieșire în cazul în care cu . 2la3b11{\ displaystyle 2 ^ {a} 3 ^ {b} 11}5q7r{\ displaystyle 5 ^ {q} 7 ^ {r}}la=bq+r{\ displaystyle a = bq + r}0≤r<d{\ displaystyle 0 \ leq r <d}

Generarea de suite

Unele programe se bucură la nesfârșit și generează secvențe infinite.

Algoritmul lui Conway al numerelor prime

Următorul program este prezentat de John Conway în cartea co-autoră cu Richard Guy Cartea numerelor . John Conway le numește „The Fantastic 14 Fractions” .

(1791,7885,1951,2338,2933,7729,9523,7719,117,1113,1311,1514,152,551){\ displaystyle \ left ({\ frac {17} {91}}, {\ frac {78} {85}}, {\ frac {19} {51}}, {\ frac {23} {38}}, {\ frac {29} {33}}, {\ frac {77} {29}}, {\ frac {95} {23}}, {\ frac {77} {19}}, {\ frac {1} {17}}, {\ frac {11} {13}}, {\ frac {13} {11}}, {\ frac {15} {14}}, {\ frac {15} {2}}, { \ frac {55} {1}} \ right)}

Acest program, aplicat întregului 2, generează o succesiune care conține toți termenii formei unde este un număr prim . În schimb, orice putere de 2 din această succesiune are un exponent de 1 sau un număr prim. Această continuare este numită jocul primar Conway . 2p{\ displaystyle 2 ^ {p}}p{\ displaystyle p}

Algoritmul este în esență un algoritm de diviziune euclidiană. Principiul este următorul: pornind de la un număr de forma unde 0 ≤ m < n , încercările algoritm divide n +1 prin toate numerele de la n la 1, până când se găsește cel mai mare număr întreg k astfel încât k se divide n + 1 și apoi se întoarce . Singurele cazuri în care algoritmul returnează o putere de 2 sunt cazurile în care k = 1, adică cazurile în care n +1 este prim. 2nu7m{\ displaystyle 2 ^ {n} 7 ^ {m}}2nu+17k-1{\ displaystyle 2 ^ {n + 1} 7 ^ {k-1}}

Secvența Fibonacci

Următorul program:

(2395,5723,1739,13017,1114,3511,1913,119,352,137,7){\ displaystyle \ left ({\ frac {23} {95}}, {\ frac {57} {23}}, {\ frac {17} {39}}, {\ frac {130} {17}}, {\ frac {11} {14}}, {\ frac {35} {11}}, {\ frac {19} {13}}, {\ frac {1} {19}}, {\ frac {35} {2}}, {\ frac {13} {7}}, 7 \ dreapta)}

aplicat întregului 3, generează o succesiune care conține toți termenii formei în care a și b sunt doi termeni consecutivi ai secvenței Fibonacci . În schimb, orice termen al secvenței formei are ca exponent doi termeni consecutivi ai secvenței Fibonacci. 2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}

Algoritmul este în esență un algoritm de adăugare care constă, începând de la furnizare . 2la3b{\ displaystyle 2 ^ {a} 3 ^ {b}}2b3la+b{\ displaystyle 2 ^ {b} 3 ^ {a + b}}

Demonstrație

Într-adevăr :

• căci fracția se transformă în , apoi fracțiile și o transformă iterativ pe aceasta din urmă în . În cazul în care ajungem direct, datorită ultimului 7 al listei;la>0{\ displaystyle a> 0}352{\ displaystyle {\ frac {35} {2}}}2la×3b{\ displaystyle 2 ^ {a} \ times 3 ^ {b}}5×7×2la-1×3b{\ displaystyle 5 \ times 7 \ times 2 ^ {a-1} \ times 3 ^ {b}}1114{\ displaystyle {\ frac {11} {14}}}3511{\ displaystyle {\ frac {35} {11}}}5la×7×3b{\ displaystyle 5 ^ {a} \ times 7 \ times 3 ^ {b}}la=0{\ displaystyle a = 0}7×3b{\ displaystyle 7 \ times 3 ^ {b}}
• Fracția se transformă apoi în , apoi fracțiile și o transformă iterativ în  ;137{\ displaystyle {\ frac {13} {7}}}5la×7×3b{\ displaystyle 5 ^ {a} \ times 7 \ times 3 ^ {b}}5la×13×3b{\ displaystyle 5 ^ {a} \ ori 13 \ ori 3 ^ {b}}1739{\ displaystyle {\ frac {17} {39}}}13017{\ displaystyle {\ frac {130} {17}}}5la+b×13×2b{\ displaystyle 5 ^ {a + b} \ ori 13 \ ori 2 ^ {b}}
• Fracția o transformă în , apoi fracțiile și o transformă în  ;1913{\ displaystyle {\ frac {19} {13}}}5la+b×19×2b{\ displaystyle 5 ^ {a + b} \ ori 19 \ ori 2 ^ {b}}2395{\ displaystyle {\ frac {23} {95}}}5723{\ displaystyle {\ frac {57} {23}}}3la+b×19×2b{\ displaystyle 3 ^ {a + b} \ times 19 \ times 2 ^ {b}}
• În cele din urmă, fracția elimină factorul 19.119{\ displaystyle {\ frac {1} {19}}}

 

Suita Syracuse

Acest program prezentat de Kenneth G. Monks:

(111,13615,517,45,2621,713,17,334,52,7){\ displaystyle \ left ({\ frac {1} {11}}, {\ frac {136} {15}}, {\ frac {5} {17}}, {\ frac {4} {5}}, {\ frac {26} {21}}, {\ frac {7} {13}}, {\ frac {1} {7}}, {\ frac {33} {4}}, {\ frac {5} {2}}, 7 \ dreapta)}

aplicat la , generează o secvență care conține succesiv toți termenii , unde b parcurge termenii secvenței Syracuse din primul termen N. În schimb, orice putere de 2 din această secvență are pentru exponent un element al secvenței Syracuse. 2NU{\ displaystyle 2 ^ {N}}2b{\ displaystyle 2 ^ {b}}

Demonstrație

• Începând de la , fracțiile și o transformă în valori crescânde ale lui k până se ajunge la dacă N este chiar egal cu 2 p sau dacă N este impar egal cu 2 p +1.2NU{\ displaystyle 2 ^ {N}}334{\ displaystyle {\ frac {33} {4}}}111{\ displaystyle {\ frac {1} {11}}}3k×2NU-2k{\ displaystyle 3 ^ {k} \ times 2 ^ {N-2k}}3p{\ displaystyle 3 ^ {p}}3p×2{\ displaystyle 3 ^ {p} \ times 2}
• În primul caz, termenul final 7 se transformă în , apoi fracțiile și îl transformă iterativ în . Fracția îndepărtează apoi 7 de prisos. Am plecat apoi de la .3p{\ displaystyle 3 ^ {p}}3p×7{\ displaystyle 3 ^ {p} \ ori 7}2621{\ displaystyle {\ frac {26} {21}}}713{\ displaystyle {\ frac {7} {13}}}2p×7{\ displaystyle 2 ^ {p} \ ori 7}17{\ displaystyle {\ frac {1} {7}}}2NU{\ displaystyle 2 ^ {N}}2NU/2{\ displaystyle 2 ^ {N / 2}}
• În al doilea caz, fracția se transformă în , apoi fracțiile și se transformă iterativ în . Ultima fracție o transformă în sfârșit în cine nu este altul decât .52{\ displaystyle {\ frac {5} {2}}}3p×2{\ displaystyle 3 ^ {p} \ times 2}3p×5{\ displaystyle 3 ^ {p} \ times 5}13615{\ displaystyle {\ frac {136} {15}}}517{\ displaystyle {\ frac {5} {17}}}5×23p{\ displaystyle 5 \ times 2 ^ {3p}}45{\ displaystyle {\ frac {4} {5}}}23p+2{\ displaystyle 2 ^ {3p + 2}}2(3NU+1)/2{\ displaystyle 2 ^ {(3N + 1) / 2}}

Astfel, exponentul N a fost modificat la N / 2 dacă N este par și (3N + 1) / 2 dacă N este impar, care este principiul secvenței Syracuse.  

Ideea lui Kenneth Monks este de a studia secvențele ciclice Syracuse căutând proprietățile secvențelor ciclice generate de acest program.

Program universal

Conway a definit, de asemenea, un program universal FRACTRAN, format din următoarele fracțiuni:

(583559,629551,437527,82517,615329,371129,1115,5386,4353,2347,34146,4143,4741,2937,3731,3731,29929,4723,16115,52719,1597,117,113,13){\ displaystyle \ left ({\ frac {583} {559}}, {\ frac {629} {551}}, {\ frac {437} {527}}, {\ frac {82} {517}}, {\ frac {615} {329}}, {\ frac {371} {129}}, {\ frac {1} {115}}, {\ frac {53} {86}}, {\ frac {43} {53}}, {\ frac {23} {47}}, {\ frac {341} {46}}, {\ frac {41} {43}}, {\ frac {47} {41}}, { \ frac {29} {37}}, {\ frac {37} {31}}, {\ frac {37} {31}}, {\ frac {299} {29}}, {\ frac {47} { 23}}, {\ frac {161} {15}}, {\ frac {527} {19}}, {\ frac {159} {7}}, {\ frac {1} {17}}, {\ frac {1} {13}}, {\ frac {1} {3}} \ right)}

Putem arăta apoi că, pentru orice funcție recursivă parțială f , există un număr întreg c astfel încât, pentru orice număr întreg n , prin aplicarea programului FRACTRAN cu lista de mai sus la număr , ajungem la numărul dacă și numai dacă calculul f ( n ) se termină. Această proprietate arată că obținem în FRACTRAN toate funcțiile calculabile. vs.×22nu{\ displaystyle c \ times 2 ^ {2 ^ {n}}}22f(nu){\ displaystyle 2 ^ {2 ^ {f (n)}}}

Note și referințe

Note

1. În articolul FRACTRAN: Un simplu limbaj universal de programare pentru aritmetică , publicat în cartea lui Cover și Gopinath, Probleme deschise în comunicare și calcul , Springer-Verlag, New York, (1987), p. 4-26.
2. (în) Algoritmi similari sunt descriși în această pagină .
3. Pentru o explicație detaliată, vezi Julian Havil, Nonplussed!: Mathematical Proof of Implausible Ideas , Princeton University Press , 2007, ( ISBN  978-0691120560 ) .

Referințe

1. Julian Havil, Nonplussed!: Mathematical Proof of Implausible Ideas , p. 162-163.
2. A se vedea continuare A007542 din OEIS .
3. (ro) [PDF] Kenneth G. Monks, „  3x + 1 minus +  ”, în Matematică discretă și informatică teoretică 5, 2002 47-54.

• (fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia din limba engleză intitulat „  FRACTRAN  ” ( vezi lista autorilor ) .

Vezi și tu

Articole similare

• număr prim
• Lista numerelor prime

Resurse bibliografice

• John Conway, „  FRACTRAN: Un limbaj de programare universal simplu pentru aritmetică  ”, în Probleme deschise în comunicare și calcul , Thomas M. Cover (corector), B. Gopinath (corector), Springer; 1 st  ed. (9 noiembrie 1987);
• Julian Havil, Nonplussed!: Mathematical Proof of Implausible Idees , Princeton University Press, 2007;
• Kenneth G. Monks, „  3x + 1 minus +  ”, în Discrete Mathematics and Theoretical Computer Science 5, 2002, 47–54.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">