FRACTRAN

FRACTRAN

FRACTRAN bir olan egzotik ve Turing-tam programlama dili için geçerli doğal tamsayılar . 1987'de bir tanımını yayınlayan matematikçi John Conway tarafından icat edildi .

Tamsayılar üzerinde herhangi bir hesaplanabilir işlevi kesirler listesi ile temsil etmekten oluşur .

A tamsayısının görüntüsünü bulmak için, A ile çarpılan kesirlerin ilki için listeye bakarız, B tamsayısı verir, sonra prosedürü tekrar B tamsayısına uygularız.Çarpılan listenin kesirlerinden hiçbiri ile çarpılırsa önceki sonuç bir tamsayı vermez, prosedür durur.

Misal

Kesirler listesine karşılık gelen FRACTRAN programını düşünün . (310,43){\ displaystyle \ sol ({\ frac {3} {10}}, {\ frac {4} {3}} \ sağ)}

Tam sayı 14'e ne tam sayı ne de tam sayı olarak uygulanırsa , program hemen durur. 310×14{\ displaystyle {\ frac {3} {10}} \ kere 14}43×14{\ displaystyle {\ frac {4} {3}} \ kere 14}

Eğer bunu 15 tamsayısına uygularsak, arka arkaya 20 (çünkü sadece biri bir tamsayıdır), sonra 6 (çünkü bir tamsayıdır), sonra 8 (çünkü sadece bir tamsayı verir), sonra prosedür durur. 43×15{\ displaystyle {\ frac {4} {3}} \ kere 15}310×20{\ displaystyle {\ frac {3} {10}} \ kere 20}43×6{\ displaystyle {\ frac {4} {3}} \ times 6}

Prensip

İlke, tamsayıların asal çarpanlarının ürünlerine ayrışmanın varlığına ve p-adik değerleme kavramına dayanmaktadır .

Her A tamsayısının, p asal sayısının üssüne A'daki p'nin değerlemesi adı verilen ve not edildiği benzersiz bir asal faktör ayrışması vardır . vp(AT){\ displaystyle v_ {p} (A)}

Belirli bir A tamsayısı için , sonlu sayıları dışında tümü sıfırdır. A tamsayısının, B tamsayısının elde edilmesini sağlayan bir kesir ile çarpılması ,. vp(AT){\ displaystyle v_ {p} (A)}vp{\ displaystyle v_ {p}}

Bu nedenle, önceki liste 2, 3 ve 5'in değerlemeleri üzerinde çalışır. İlk fraksiyon 1'i 2 ve 5'in değerlemelerinden çıkarır (bu mümkünse) ve 3'ün değerini 1'e yükseltir, ikinci fraksiyon yalnızca değerleme 2 veya 5 sıfır ise, 2'nin değerini iki birim artırır ve 3'ün değerini bir birim azaltır.

A, A '30 ile üssü ile yazıldığında ve iki döngü kullanarak, prosedür A'yı sonra'ya dönüştürür ve sonra durur. 2-de×3b×5vs×AT′{\ displaystyle 2 ^ {a} \ times 3 ^ {b} \ times 5 ^ {c} \ times A '}vs≤-de{\ displaystyle c \ leq a}B=2-de-vs×3b+vs×AT′{\ displaystyle B = 2 ^ {ac} \ times 3 ^ {b + c} \ times A '}2-de+2b+vs×AT′{\ displaystyle 2 ^ {a + 2b + c} \ times A '}

Program böylece değerlemeler üzerinde işlemlerin tanımlanmasını mümkün kılar.

Temel işlemler

İlave

Tek kesiri içeren liste , 2 ve 3'ün değerlemelerini toplamayı mümkün kılar: A, 6 ile A 'üssü ile yazıldığında , prosedür A'ya dönüşene kadar uygulanır . 32{\ displaystyle {\ frac {3} {2}}}2-de×3b×AT′{\ displaystyle 2 ^ {a} \ times 3 ^ {b} \ times A '}3-de+b×AT′{\ displaystyle 3 ^ {a + b} \ times A '}

Çarpma işlemi

Ek bir döngü kullanarak çarpımsal bir fonksiyon oluşturabiliriz. Bunun için algoritmaya durum kavramını eklemek gerekir . Bu algoritma bir sayıya uygulanır ve onu 2, 3, 5 ve ayrıca 7, 11 ve 13 değerlerine dönüştürür ve üzerinde çalışır: 2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}5-deb{\ displaystyle 5 ^ {ab}}

Şu anki durum	Durum	Aksiyon	Sonraki durum
AT	v7> 0	1’den v7’ye 1’i v3’e ekle	AT
	v7 = 0 ve v2> 0	V2'den 1 çıkar	B
	v7 = 0 ve v2 = 0 ve v3> 0	V3'ten 1 çıkar	AT
	v7 = 0 ve v2 = 0 ve v3 = 0	Dur
B	v3> 0	1'i v3'ten çıkarın 1'i v5'e ekleyin 1'i v7'ye ekleyin	B
	v3 = 0	Hiçbir şey değil	AT

Durum B, v3'ü v5'e ekleyen ve ayrıca v3'ü v7'ye taşıyan bir döngüdür ve A durumu, döngü B v2'yi tekrarlayan bir döngüdür. Durum A ayrıca, döngü B sonlandırıldığında başlangıç ​​değerini (v7'de bulunan) v3'e döndürür.

Bu durumları yönetmek için yeni değişkenler gereklidir: durum göstergeleri rolünü oynarlar. Döngü B'nin durum bayrakları v11 ve v13'tür. Tek döngü B için iki durum göstergesi gereklidir: aslında, döngünün girişinde tüketilen ilk gösterge (v11), programa devam etmesi gerektiğini belirtmek için ikinci bir göstergeye (v13) sahip olmak gerekir. aynı durum. V13 bayrağı, döngünün "sonraki" ifadesi sırasında v11 olarak değiştirilir.

Durum göstergelerini ve talimatları çarpma algoritması tablosuna ekleyerek şunları elde ederiz:

talimat frakranı	Şu anki durum	Durum göstergeleri	Durum	Aksiyon	Sonraki durum
37{\ displaystyle {\ frac {3} {7}}}	AT	Hayır	v7> 0	V7'den 1 çıkar, v3'ten 1 ekle	AT
112{\ displaystyle {\ frac {11} {2}}}			v7 = 0 ve v2> 0	V2'den 1'i çıkar, v11'i 1'e ayarla	B
13{\ displaystyle {\ frac {1} {3}}}			v7 = 0 ve v2 = 0 ve v3> 0	V3'ten 1 çıkar	AT
			v7 = 0 ve v2 = 0 ve v3 = 0	Dur
5⋅7⋅133⋅11,1113{\ displaystyle {\ frac {5 \ cdot 7 \ cdot 13} {3 \ cdot 11}}, {\ frac {11} {13}}}	B	s11, s13	v3> 0	1'i v3'ten çıkarın 1'i v5'e ekleyin 1'i v7'ye ekleyin	B
111{\ displaystyle {\ frac {1} {11}}}			v3 = 0	V11'i 0 olarak ayarlayın	AT

FRACTRAN komutlarının listesini yazarken, durum A'nın komutlarını en son koymalıyız çünkü durum A'da durum göstergesi yoktur, varsayılan durumdur.

Bu nedenle FRACTRAN çarpma programı aşağıdaki listedir:

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

Numarayı girerseniz program geri döner . 2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}5-deb{\ displaystyle 5 ^ {ab}}

Çıkarma

Basit bir fraksiyon sayısı dönüştürür içine 16{\ displaystyle {\ frac {1} {6}}}2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}

• 2-de-b30{\ displaystyle 2 ^ {ab} 3 ^ {0}}, eğer  ;-de>b{\ displaystyle a> b}
• 203b--de{\ displaystyle 2 ^ {0} 3 ^ {ba}}, eğer  ;b>-de{\ displaystyle b> a}
• 2030{\ displaystyle 2 ^ {0} 3 ^ {0}}evet .-de=b{\ displaystyle a = b}

Öklid bölümü

Öklid bölme arasında bir ile b ( a ve b doğal sayılar, b > 1), doğal verilmektedir numaraları q ve r , öyle ki R < b ve a = bq + r . Bu Öklid bölünme çok çıkarma bir döngü olarak görülebilir: bölünmesi bir göre b olup çıkarmak için , b ile ilgili olarak gerekli olduğu kadar çok kez, bu çıkartma, tekabül gerçekleştirilir sayısı q , son değer bir dinlenme eşleşir.

Algoritma daha sonra a , v3 içeren b , q içermesi amaçlanan v5 ve r içermesi amaçlanan v7 üzerinde çalışır . Bu değişkenler 4 durum göstergesi v11, v13, v17, v19 ile desteklenir.

Aşağıdaki FRACTRAN programı üç durumdan oluşur:

• durum A, v3'ün v2'den küçük veya büyük olmasına bağlı olarak farklı şekilde çalışır;
  • eğer v3 ≤ v2 ise, döngü v3'ü v2'den çıkarır, v7'de v3'ü boşaltır, 1'i v5'e ekler ve B durumuna geçer;
  • v3> v2 ise, v2 döngüsü v7'ye boşalır ve X durumuna geçer.
• durum B, daha önce v7'yi v3'e boşalttıktan sonra A döngüsünü yeniden gerçekleştiren bir aşırı döngüdür;
• X durumu, v2 boş olduğunda ve v3 boş olmadığında v3'ün boşaltılmasını içerir.

FRACTRAN talimatları	Şu anki durum	Durum göstergeleri	şartlar ve koşullar	Hareketler	Sonraki durum
7⋅132⋅3⋅11,1113{\ displaystyle {\ frac {7 \ cdot 13} {2 \ cdot 3 \ cdot 11}}, {\ frac {11} {13}}}	AT	s11, s13	v2> 0 ve v3> 0	V2'den 1 çıkar, v3'ten 1 çıkar, v7'den 1 ekle	AT
13⋅11{\ displaystyle {\ frac {1} {3 \ cdot 11}}}			v2 = 0 ve v3> 0	V3'ten 1 çıkar, v11'i 0'a ayarla	X
5⋅1711{\ displaystyle {\ frac {5 \ cdot 17} {11}}}			v3 = 0	1’den v5’e ekle v11’i 0’a ayarla v17’yi 1’e ayarla	B
3⋅197⋅17,1719{\ displaystyle {\ frac {3 \ cdot 19} {7 \ cdot 17}}, {\ frac {17} {19}}}	B	s17, s19	v7> 0	V7'den 1 çıkar, v3'ten 1 ekle	B
1117{\ displaystyle {\ frac {11} {17}}}			v7 = 0	V11'i 1'e ayarlayın v17'yi 0'a ayarlayın	AT
13{\ displaystyle {\ frac {1} {3}}}	X		v3> 0	V3'ten 1 çıkar	X
			v3 = 0	Dur

Programın yazımı daha sonra:

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

Sen girmek zorunda sadece çıkmak almak için nereye ile . 2-de3b11{\ displaystyle 2 ^ {a} 3 ^ {b} 11}5q7r{\ displaystyle 5 ^ {q} 7 ^ {r}}-de=bq+r{\ displaystyle a = bq + r}0≤r<d{\ displaystyle 0 \ leq r <d}

Süit üretimi

Bazı programlar süresiz olarak döngü yapar ve sonsuz dizi oluşturur.

Conway'in asal sayı algoritması

Aşağıdaki program, Richard Guy The Book of Numbers ile birlikte yazılan kitapta John Conway tarafından sunulmuştur . John Conway onlara "Fantastik 14 Kesirler" diyor .

(1791,7885,1951,2338,2933,7729,9523,7719,117,1113,1311,1514,152,551){\ displaystyle \ sol ({\ 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}} \ sağ)}

2 tamsayısı uygulanan bu program, formunun bütün şartlarını içeren bir dizi üreten bir olan asal sayı . Tersine, bu dizideki herhangi bir 2'nin üssü 1 veya bir asal sayıya sahiptir. Bu devam oyunun adı Conway primegame . 2p{\ displaystyle 2 ^ {p}}p{\ displaystyle p}

Algoritma esasen bir Öklid bölünme algoritmasıdır. Şeklinde bir dizi başlayarak: prensibi aşağıdaki gibidir , burada 0 ≤ m < n , bölmek için algoritma çalışır n tüm numaraları ile + 1 n o en büyük tam sayıyı bulana kadar 1, k , öyle ki k böler n + 1 ve sonra geri döner . Algoritmanın 2 kuvvetini döndürdüğü tek durum, k = 1 olduğu durumlardır , yani n + 1'in asal olduğu durumlardır . 2değil7m{\ displaystyle 2 ^ {n} 7 ^ {m}}2değil+17k-1{\ displaystyle 2 ^ {n + 1} 7 ^ {k-1}}

Fibonacci Dizisi

Aşağıdaki program:

(2395,5723,1739,13017,1114,3511,1913,119,352,137,7){\ displaystyle \ sol ({\ 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 \ sağ)}

3 tamsayısına uygulandığında, a ve b'nin Fibonacci dizisinin iki ardışık terimi olduğu formun tüm terimlerini içeren bir dizi oluşturur . Tersine, form dizisinin herhangi bir terimi , Fibonacci dizisinin iki ardışık terimine üslü olarak sahiptir. 2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}

Algoritma, temelde sağlamaktan başlayarak oluşan bir toplama algoritmasıdır . 2-de3b{\ displaystyle 2 ^ {a} 3 ^ {b}}2b3-de+b{\ displaystyle 2 ^ {b} 3 ^ {a + b}}

Gösteri

Aslında :

• için , fraksiyon dönüşümleri içine , daha sonra kısımlar ve yinelemeli ikinci dönüşmek . Listenin son 7'si sayesinde doğrudan ulaşmamız durumunda ;-de>0{\ displaystyle a> 0}352{\ displaystyle {\ frac {35} {2}}}2-de×3b{\ displaystyle 2 ^ {a} \ times 3 ^ {b}}5×7×2-de-1×3b{\ displaystyle 5 \ times 7 \ times 2 ^ {a-1} \ times 3 ^ {b}}1114{\ displaystyle {\ frac {11} {14}}}3511{\ displaystyle {\ frac {35} {11}}}5-de×7×3b{\ displaystyle 5 ^ {a} \ times 7 \ times 3 ^ {b}}-de=0{\ displaystyle a = 0}7×3b{\ displaystyle 7 \ times 3 ^ {b}}
• Fraksiyon daha sonra dönüşümleri içine daha sonra fraksiyonlar, ve yinelemeli dönüştürür  ;137{\ displaystyle {\ frac {13} {7}}}5-de×7×3b{\ displaystyle 5 ^ {a} \ times 7 \ times 3 ^ {b}}5-de×13×3b{\ displaystyle 5 ^ {a} \ times 13 \ times 3 ^ {b}}1739{\ displaystyle {\ frac {17} {39}}}13017{\ displaystyle {\ frac {130} {17}}}5-de+b×13×2b{\ displaystyle 5 ^ {a + b} \ times 13 \ times 2 ^ {b}}
• Kesir onu , sonra kesirleri dönüştürür ve şu şekle dönüştürür  ;1913{\ displaystyle {\ frac {19} {13}}}5-de+b×19×2b{\ displaystyle 5 ^ {a + b} \ times 19 \ times 2 ^ {b}}2395{\ displaystyle {\ frac {23} {95}}}5723{\ displaystyle {\ frac {57} {23}}}3-de+b×19×2b{\ displaystyle 3 ^ {a + b} \ times 19 \ times 2 ^ {b}}
• Son olarak, kesir , faktör 19'u kaldırır.119{\ displaystyle {\ frac {1} {19}}}

 

Syracuse Süit

Kenneth G. Monks tarafından sunulan bu program:

(111,13615,517,45,2621,713,17,334,52,7){\ displaystyle \ sol ({\ 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 \ sağ)}

uygulandığında , ardışık olarak tüm terimleri içeren bir dizi oluşturur ; burada b , ilk terim N'nin Syracuse dizisinin terimlerini çaprazlar. Tersine, bu dizideki herhangi bir 2'nin üssü Syracuse dizisinin bir elemanına sahiptir. 2DEĞİL{\ displaystyle 2 ^ {N}}2b{\ displaystyle 2 ^ {b}}

Gösteri

• Başlayarak , kesirler ve onu artan k değerleri için, N 2 p'ye eşitse veya N 2 p + 1'e eşitse tek sayıya ulaşana kadar dönüştürür .2DEĞİL{\ displaystyle 2 ^ {N}}334{\ displaystyle {\ frac {33} {4}}}111{\ displaystyle {\ frac {1} {11}}}3k×2DEĞİL-2k{\ displaystyle 3 ^ {k} \ times 2 ^ {N-2k}}3p{\ displaystyle 3 ^ {p}}3p×2{\ displaystyle 3 ^ {p} \ times 2}
• İlk durumda, son dönem 7 dönüşümler içine , daha sonra kısımlar ve yinelemeli dönüştürür . Kesir daha sonra gereksiz 7'yi kaldırır. Sonra gitti etmek .3p{\ displaystyle 3 ^ {p}}3p×7{\ displaystyle 3 ^ {p} \ times 7}2621{\ displaystyle {\ frac {26} {21}}}713{\ displaystyle {\ frac {7} {13}}}2p×7{\ displaystyle 2 ^ {p} \ times 7}17{\ displaystyle {\ frac {1} {7}}}2DEĞİL{\ displaystyle 2 ^ {N}}2DEĞİL/2{\ displaystyle 2 ^ {N / 2}}
• İkinci durumda, fraksiyon dönüşümleri içine , daha sonra kısımlar ve içine iteratif dönüşümler . Son fraksiyon nihayet onu başkası olmayan birine dönüştürür .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(3DEĞİL+1)/2{\ displaystyle 2 ^ {(3N + 1) / 2}}

Bu nedenle, N üssü N çift ise N / 2 ve N tek ise (3N + 1) / 2 olarak modifiye edilmiştir ki bu Syracuse dizisinin ilkesidir.  

Kenneth Monks'un fikri, bu program tarafından üretilen döngüsel dizilerin özelliklerini arayarak döngüsel Syracuse dizilerini incelemektir.

Evrensel program

Conway ayrıca aşağıdaki kesirlerden oluşan evrensel bir FRACTRAN programı tanımlamıştır:

(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 \ sol ({\ 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}} \ sağ)}

Daha sonra, herhangi bir özyinelemeli kısmi fonksiyon f için, herhangi bir n tamsayısı için , yukarıdaki listeyle birlikte FRACTRAN programını sayıya uygulayarak , sayıya ancak ve ancak hesaplama yapılırsa ulaşacağımız şekilde bir c tamsayısının var olduğunu gösterebiliriz . f ( n ) biter. Bu özellik, tüm hesaplanabilir fonksiyonları FRACTRAN'da elde ettiğimizi gösterir. vs×22değil{\ displaystyle c \ times 2 ^ {2 ^ {n}}}22f(değil){\ displaystyle 2 ^ {2 ^ {f (n)}}}

Notlar ve referanslar

Notlar

1. Kapak ve Gopinath'ın kitabında yayınlanan FRACTRAN: Aritmetik için basit bir evrensel programlama dili makalesinde , İletişim ve Hesaplamada Açık Sorunlar , Springer-Verlag, New York, (1987), s. 4-26.
2. (inç) Benzer algoritmalar bu sayfada açıklanmıştır .
3. Ayrıntılı bir açıklama için bkz. Julian Havil, Nonplussed!: Mathematical Proof of Implausible Ideas , Princeton University Press , 2007, ( ISBN  978-0691120560 ) .

Referanslar

1. Julian Havil, Nonplussed!: Mathematical Proof of Implausible Ideas , s. 162-163.
2. devamı Bkz A007542 ait OEIS .
3. (en) [PDF] Kenneth G. Monks, "  3x + 1 minus the +  ," in Discrete Mathematics and Theoretical Computer Science 5, 2002 47-54.

• (fr) Bu makale kısmen veya tamamen Wikipedia makalesinden alınmıştır İngilizce başlıklı "  FRACTRAN  " ( yazarların listesini görmek ) .

Ayrıca görün

İlgili Makaleler

• asal sayı
• Asal sayıların listesi

Bibliyografik kaynaklar

• John Conway, "  FRACTRAN: Aritmetik için basit bir evrensel programlama dili  ", İletişim ve Hesaplamada Açık Sorunlar , Thomas M. Cover (düzeltici), B. Gopinath (düzeltici), Springer; 1 st  ed. (9 Kasım 1987);
• Julian Havil, Plussed!: Mantıksız Fikirlerin Matematiksel Kanıtı , Princeton University Press, 2007;
• Kenneth G. Monks, "  3x + 1 eksi +  ", Ayrık Matematik ve Teorik Bilgisayar Bilimleri 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;">