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:

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

b_n Aks holda = 0;

uchun n ≥ 0.^[1]

Masalan, b₄ = 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 b₅ = 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 ${displaystyle mathbb {F} _ {2} ((X ^ {- 1}))}$ 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

${displaystyle f ^ {3} + x ^ {- 1} f + 1 = 0.}$^[2][5]

Mualliflar buni ko'rsatib turibdi Gensel lemmasi, bunday noyob ildiz mavjud ${displaystyle mathbb {F} _ {2} ((X ^ {- 1}))}$ chunki ning aniqlovchi tenglamasini kamaytirish ${displaystyle f}$ modul ${displaystyle X ^ {- 1}}$ beradi ${displaystyle f ^ {3} +1}$, bu kabi omillar

${displaystyle f ^ {3} + 1 = (f + 1) (f ^ {2} + f + 1).}$

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

${displaystyle f = sum _ {kgeq 0} f_ {i} X ^ {- k}}$

qayerda ${displaystyle f_ {0} = 1}$ va ${displaystyle f_ {k} = 1}$ uchun ${displaystyle kgeq 1}$ va agar ikkilik kengayish bo'lsa ${displaystyle n}$ ning faqat uzunlikdagi bloklarini o'z ichiga oladi ${displaystyle 0}$. Bu Baum-Sweet ketma-ketligining kelib chiqishi.

Mkaouar^[6] va Yao^[7] uchun davom etgan kasrning qisman kvotalari isbotlandi ${displaystyle f}$ 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 b_n Baum-Shirin ketma-ketlikda quyidagicha rekursiv tarzda topish mumkin. Agar n = m·4^k, qayerda m 4 ga bo'linmaydi (yoki 0 ga teng), keyin

${displaystyle b_ {n} = {egin {case} 1 & {ext {if}} n = 0 0 & {ext {if}} m {ext {even}} b _ {(m-1) / 2} & {ext {if}} m {ext {g'alati}}. end {case}}}$

Shunday qilib b₇₆ = b₉ = b₄ = b₀ = 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 (b_n Hammasi uchun = 0^k 5.2 oralig'idagi butun sonlar^k ≤ n < 6.2^k), lekin unda ketma-ket uchta sonli blok yo'q.

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

${displaystyle varphi (A) = AB, varphi (B) = CB, varphi (C) = BD, varphi (D) = DD}$

va kodlash

${displaystyle au (A) = 1, au (B) = 1, au (C) = 0, au (D) = 0}$

so'zni shu tarzda yarating.^[10]

Izohlar

Adabiyotlar

• Alloush, Jan-Pol; Shallit, Jefri (2003). Avtomatik ketma-ketliklar: nazariya, qo'llanmalar, umumlashtirish. Kembrij universiteti matbuoti. ISBN  978-0-521-82332-6. Zbl  1086.11015.