Baum - Shirin ketma-ketlik - Baum–Sweet sequence

Yilda matematika The Baum - Shirin ketma-ketlik cheksizdir avtomatik ketma-ketlik qoida bilan belgilangan 0 va 1 sonlari:

bn = Ning ikkilik vakili bo'lsa n tarkibida toq uzunlikdagi ketma-ket 0 lar yo'q;
bn Aks holda = 0;

uchun n ≥ 0.[1]

Masalan, b4 = 1, chunki 4 ning ikkilik vakili 100 ga teng bo'lib, u faqat 2 uzunlikdagi ketma-ket 0 larning bitta blokini o'z ichiga oladi; Holbuki b5 = 0, chunki 5 ning ikkilik vakolatxonasi 101 ga teng bo'lib, unda ketma-ket 1 uzunlikdagi 0s blok mavjud.

Boshlanishi n = 0, Baum-Sweet ketma-ketligining dastlabki bir nechta shartlari:

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (ketma-ketlik A086747 ichida OEIS )

Tarixiy motivatsiya

Ketma-ketlikning xususiyatlari birinchi marta L.E. Baum va M.M. 1976 yilda shirin.[2] 1949 yilda Xinchin fraksiya kengayishida chegaralangan kvotentlarga ega kvadratik bo'lmagan algebraik haqiqiy son yo'q deb taxmin qildi. Ushbu gumonga qarshi misol hali ham ma'lum emas.[3][4] Baum va Sweetning maqolalari shuni ko'rsatdiki, algebraik kuchlar seriyasida ham xuddi shu umid kutilmagan. Ular kubik quvvat seriyasiga misol keltirdilar uning qisman kotirovkalari chegaralangan. (Baum va Sweet natijalaridagi quvvat seriyasining darajasi, Xinchin taxminida algebraik real bilan bog'liq maydon kengayish darajasiga o'xshashdir.)

Baum va Sweetning maqolalarida ko'rib chiqilgan seriyalardan biri bu ildiz

[2][5]

Mualliflar buni ko'rsatib turibdi Gensel lemmasi, bunday noyob ildiz mavjud chunki ning aniqlovchi tenglamasini kamaytirish modul beradi , bu kabi omillar

Ular ushbu noyob ildizning daraja qisman kvotalariga ega ekanligini isbotlashga kirishadilar . Bunga qadar ular (2-teoremadan keyingi izohda, 598-bet)[2] ildiz shaklda yozilishi mumkinligi

qayerda va uchun va agar ikkilik kengayish bo'lsa ning faqat uzunlikdagi bloklarini o'z ichiga oladi . Bu Baum-Sweet ketma-ketligining kelib chiqishi.

Mkaouar[6] va Yao[7] uchun davom etgan kasrning qisman kvotalari isbotlandi yuqorida avtomatik ketma-ketlikni hosil qilmaydi.[8] Biroq, qisman kotirovkalarning ketma-ketligini bir xil bo'lmagan morfizm hosil qilishi mumkin.[9]

Xususiyatlari

Baum-Sweet ketma-ketligini 3-holat yaratishi mumkin avtomat.[9]

Muddatning qiymati bn Baum-Shirin ketma-ketlikda quyidagicha rekursiv tarzda topish mumkin. Agar n = m·4k, qayerda m 4 ga bo'linmaydi (yoki 0 ga teng), keyin

Shunday qilib b76 = b9 = b4 = b0 = 1, buni 76 ning ikkilik vakolatxonasida 1001100 ga teng bo'lgan 0s ning ketma-ket bloklari mavjud emasligini kuzatish orqali tekshirish mumkin.

Baum-Sweet ketma-ketligi shartlarini birlashtirish orqali hosil bo'lgan Baum – Shirin so'z 1101100101001001 ... morfizmning sobit nuqtasidir yoki mag'lubiyatni almashtirish qoidalar

00 0000
01 1001
10 0100
11 1101

quyidagicha:

11 1101 11011001 1101100101001001 11011001010010011001000001001001 ...

Morfizm qoidalaridan ko'rinib turibdiki, Baum-Sweet so'zida istalgan uzunlikdagi ketma-ket 0 sonli bloklar mavjud (bn Hammasi uchun = 0k 5.2 oralig'idagi butun sonlarkn < 6.2k), lekin unda ketma-ket uchta sonli blok yo'q.

Yana qisqacha, tomonidan Kobxemning kichik teoremasi Baum-Shirin so'z kodlash shaklida ifodalanishi mumkin bir xil morfizmning sobit nuqtasiga qo'llaniladi . Darhaqiqat, morfizm

va kodlash

so'zni shu tarzda yarating.[10]

Izohlar

  1. ^ Vayshteyn, Erik V. "Baum - Shirin ketma-ketlik". MathWorld.
  2. ^ a b v Baum, Leonard E.; Shirin, Melvin M. (1976). "Algebraik quvvat seriyasining davomli kasrlari 2-xarakteristikada". Matematika yilnomalari. 103 (3): 593–610. doi:10.2307/1970953. JSTOR  1970953.
  3. ^ Valdschmidt, M. (2009). "So'zlar va transsendensiya". W.W.L.da Chen; V.T.Govers; X. Halbertstam; V.M. Shmidt; R.C. Vaughan (tahrir). Analitik raqamlar nazariyasi: Klaus Rot sharafiga insholar (PDF). Kembrij universiteti matbuoti. 31-bo'lim, p. 449-470.
  4. ^ Xinchin, A.I. (1964). Davomiy kasrlar. Chikago universiteti matbuoti.
  5. ^ Grem Everest, Alf van der Poorten, Igor Shparlinski, Tomas Vard Takrorlanish ketma-ketliklari AMS 2003, 236-bet.
  6. ^ Mkaouar, M. (1995). "Sur le développement en fraction de la série de Baum et Sweet". Buqa. Soc. Matematika. Frantsiya. 123 (3): 361–374. doi:10.24033 / bsmf.2264.
  7. ^ Yao, J.-Y. (1997). "Critères de non-automaticité et leurs ilovalar". Acta Arith. 80 (3): 237–248. doi:10.4064 / aa-80-3-237-248.
  8. ^ Allouche and Shallit (2003) 210-bet.
  9. ^ a b Allouche, J .-. P. (1993). "Sonli avtomatika va arifmetika". Séminaire Lotaringien de Kombinatuar: 23.
  10. ^ Allouche and Shallit (2003) 176-bet.

Adabiyotlar