Avtomatik ketma-ketlik - Automatic sequence

Yilda matematika va nazariy informatika, an avtomatik ketma-ketlik (shuningdek, a k-avtomatik ketma-ketlik yoki a k- taniqli ketma-ketlik ishlatilgan raqamlarning asosi ekanligini ko'rsatmoqchi bo'lganda k) cheksizdir ketma-ketlik bilan tavsiflangan atamalar cheklangan avtomat. The n- avtomatik ketma-ketlikning uchinchi davri a(n) bu raqamlarning raqamlarini qabul qiladigan cheklangan avtomatlarda erishilgan yakuniy holatning xaritasi n ba'zilarida sobit tayanch  k.^[1][2]

An avtomatik to'plam manfiy bo'lmagan butun sonlar to'plamidir S buning uchun uning xarakterli funktsiyasi qiymatlari ketma-ketligi χ_S avtomatik ketma-ketlik; anavi, S bu kaut bo'lsa avtomatik_S(n) k-avtomatik, bu erda χ_S(n) = 1 agar n ${displaystyle in}$ S aks holda 0.^[3][4]

Ta'rif

Avtomatik ketma-ketliklar bir nechta usulda aniqlanishi mumkin, ularning barchasi tengdir. To'rtta umumiy ta'riflar quyidagicha.

Avtomatik-nazariy

Ruxsat bering k ijobiy bo'ling tamsayı va ruxsat bering D. = (Q, Σ_k, δ, q₀, Δ, τ) bo'lishi a aniqlangan cheklangan avtomat chiqishi bilan, qayerda

• Q cheklangan o'rnatilgan davlatlar;
• kirish alifbosi Σ_k {0,1, ..., to'plamidan iboratkMumkin bo'lgan raqamlarning -1} tayanch -k yozuv;
• δ: Q × Σ_k → Q o'tish funktsiyasi;
• q₀ ∈ Q dastlabki holat;
• chiqish alifbosi a cheklangan to'plam; va
• τ: Q → Δ - bu ichki holatlar to'plamidan chiqish alfavitigacha chiqish funktsiyasini xaritalash.

The ning o'tish funktsiyasini bitta raqamga ta'sir qilishdan raqamlar qatorida ishlashga kengaytiring s raqamlardan iborat s₁s₂...s_t kabi:

δ (q,s) = δ (δ (q₀, s₁s₂...s_t-1), s_t).

Funktsiyani aniqlang a musbat tamsayılar to'plamidan chiqish alifbosiga Δ quyidagicha:

a(n) = τ (δ (q₀,s(n))),

qayerda s(n) n bazada yozilgan k. Keyin ketma-ketlik a = a(1)a(2)a(3) ... bu a k-avtomatik ketma-ketlik.^[1]

Baza o'qiydigan avtomat k ning raqamlari s(n) eng muhim raqamdan boshlab deyiladi to'g'ridan-to'g'ri o'qish, eng kichik raqamdan boshlangan avtomat esa teskari o'qish.^[4] Yuqoridagi ta'rifda "yo'q" degan ma'noni anglatadi s(n) to'g'ridan-to'g'ri yoki teskari o'qishdir.^[5]

O'zgartirish

Ruxsat bering ${displaystyle varphi}$ bo'lishi a k-bir xil morfizm a bepul monoid ${displaystyle Sigma ^ {*}}$ va ruxsat bering ${displaystyle au}$ bo'lishi a kodlash (ya'ni, a ${displaystyle 1}$-bir xil morfizm), xuddi avtomat-teoretik holatdagi kabi. Agar ${displaystyle w}$ a sobit nuqta ning ${displaystyle varphi}$- ya'ni, agar ${displaystyle w = varphi (w)}$- keyin ${displaystyle s = au (w)}$ a k-avtomatik ketma-ketlik.^[6] Aksincha, har biri k-avtomatik ketma-ketlikni shu tarzda olish mumkin.^[4] Ushbu natija Kobemga bog'liq bo'lib, u adabiyotda shunday nomlanadi Kobxemning kichik teoremasi.^[2][7]

k- yadro

Ruxsat bering k ≥ 2. The k-yadrosi ketma-ketlik s(n) - bu ketma-ketliklar to'plami

${displaystyle K_ {k} (s) = {s (k ^ {e} n + r): egeq 0 {ext {and}} 0leq rleq k ^ {e} -1}.}$

Ko'p hollarda, kketma-ketlik yadrosi cheksizdir. Ammo, agar k-kernel cheklangan, keyin ketma-ketlik s(n) k-avtomatik va teskari tomon ham to'g'ri. Bu Eilenberg bilan bog'liq.^[8][9][10]

Bundan kelib chiqadiki, a k-avtomatik ketma-ketlik bu cheklangan alfavitdagi ketma-ketlikdir.

Rasmiy quvvat seriyalari

Ruxsat bering siz(n) alfavit bo'yicha ketma-ketlik bo'lsin va u mavjud deb taxmin qiling in'ektsiya funktsiyasi β dan. gacha cheklangan maydon F_q, qayerda q = pⁿ ba'zi bir yaxshi narsalar uchun p. Bilan bog'liq rasmiy quvvat seriyalari bu

${displaystyle sum _ {igeq 0} eta (u (i)) X ^ {i}.}$

Keyin ketma-ketlik siz bu q- agar bu rasmiy quvvat seriyasi bo'lsa va faqat avtomatik bo'lsa algebraik ustida F_q(X). Ushbu natija Kristolga bog'liq bo'lib, u adabiyotda shunday nomlanadi Kristol teoremasi.^[11]

Tarix

Avtomatik ketma-ketliklar tomonidan kiritilgan Büchi 1960 yilda,^[12] garchi uning maqolasi bu masalada ko'proq mantiqiy-nazariy yondashuvni qo'llagan bo'lsa va ushbu maqolada keltirilgan terminologiyadan foydalanilmagan bo'lsa ham. Avtomatik ketma-ketlik tushunchasi 1972 yilda Cobham tomonidan yana o'rganilib, ushbu ketma-ketliklarni "bir xil" deb atagan teglar ketma-ketligi ".^[7]

"Avtomatik ketma-ketlik" atamasi birinchi marta Deshouillers maqolasida paydo bo'ldi.^[13]

Misollar

Quyidagi ketma-ketliklar avtomatik:

Thue-Morse ketma-ketligi

Thue-Morse ketma-ketligini yaratadigan DFAO

The Thue-Morse ketma-ketligi t(n) (OEIS: A010060) bo'ladi sobit nuqta morfizmining 0 → 01, 1 → 10. dan beri nThue-Morse ketma-ketligining uchinchi davri ularning sonini hisoblaydi modul Ning asosi-2 tasvirida 2 n, u ikki holatli deterministik cheklangan avtomat tomonidan ishlab chiqarilgan bo'lib, bu erda tasvirlangan q₀ ning tasvirida bir juft son mavjudligini bildiradi n va davlatda bo'lish q₁ ularning toq soni borligini bildiradi, shuning uchun Thue-Morse ketma-ketligi 2 ta avtomatdir.

Davrni ikki baravar oshirish

The n- davrni ikki baravar oshirish ketma-ketligining uchinchi muddati d(n) (OEIS: A096268) 2 ga bo'linishning eng yuqori kuchi ko'rsatkichi tengligi bilan belgilanadi n. Bundan tashqari, u 0 → 01, 1 → 00 morfizmning sobit nuqtasidir.^[14] Dastlabki muddatdan boshlab w = 0 va $ 2 $ ga teng bo'lgan morfizmni takrorlang w bu erda φ (0) = 01 va φ (1) = 00 bo'lsa, davrni ikki baravar oshirish ketma-ketligi () ning sobit nuqtasi ekanligi ravshan.w) va shuning uchun u 2 avtomatik.

Rudin-Shapiro ketma-ketligi

The n- ning uchinchi davri Rudin-Shapiro ketma-ketligi r(n) (OEIS: A020985) ning asos-2 tasviridagi ketma-ket soni bilan aniqlanadi n. Rudin-Shapiro ketma-ketligining 2 yadrosi^[15] bu

${displaystyle {egin {hizalanmış} r (2n) & = r (n), r (4n + 1) & = r (n), r (8n + 7) & = r (2n + 1), r (16n + 3) & = r (8n + 3), r (16n + 11) & = r (4n + 3) .end {hizalangan}}}$

Chunki 2 yadroli faqat r(n), r(2n + 1), r(4n + 3) va r(8n + 3), u cheklangan va shuning uchun Rudin-Shapiro ketma-ketligi 2 avtomatdir.

Boshqa ketma-ketliklar

Ikkalasi ham Baum - Shirin ketma-ketlik^[16] (OEIS: A086747) va muntazam qog'oz qog'ozlarini ketma-ketligi^[17][18][19] (OEIS: A014577) avtomatik. Bundan tashqari, buklanishlarning davriy ketma-ketligi bilan umumiy qog'oz varag'i ketma-ketligi ham avtomatik.^[20]

Xususiyatlari

Avtomatik ketma-ketliklar bir qator qiziqarli xususiyatlarni namoyish etadi. Ushbu xususiyatlarning to'liq bo'lmagan ro'yxati quyida keltirilgan.

• Har bir avtomatik ketma-ketlik a morfik so'z.^[21]
• Uchun k ≥ 2 va r ≥ 1, ketma-ketlik k-avtomatik va agar shunday bo'lsa k^r-avtomatik. Ushbu natija Eilenbergga tegishli.^[22]
• Uchun h va k multiplikativ jihatdan mustaqil, ketma-ketlik ikkalasi h-avtomatik va k- agar u oxir-oqibat davriy bo'lsa va faqat avtomatik bo'lsa.^[23] Ushbu natijaga Kobxem sabab bo'ldi,^[24] Semenov tufayli ko'p o'lchovli umumlashtirish bilan.^[25][26]
• Agar siz(n) a k- alfavit bo'yicha avtomatik ketma-ketlik Σ va f a bir xil morfizm Σ dan^∗ boshqa alifboga Δ^∗, keyin f(siz) a k- Δ dan yuqori avtomatik ketma-ketlik.^[27]
• Agar siz(n) a k-avtomatik ketma-ketlik, keyin ketma-ketliklar siz(kⁿ) va siz(kⁿ - 1) oxir-oqibat davriydir.^[28] Aksincha, agar siz(n) bu oxir-oqibat davriy ketma-ketlik, keyin ketma-ketlik v tomonidan belgilanadi v(kⁿ) = siz(n) aks holda nol bo'ladi k-avtomatik.^[29]

Avtomatlikni isbotlash va rad etish

Nomzodlar ketma-ketligi berilgan ${displaystyle s = (s_ {n}) _ {ngeq 0}}$, odatda, uning avtomatikligini isbotlashdan ko'ra uni rad etish osonroq. Tomonidan k-kernel tavsifi k-avtomatik ketma-ketliklar, ichida cheksiz ko'p aniq elementlarni hosil qilish kifoya k- yadro ${displaystyle K_ {k} (lar)}$ buni ko'rsatish uchun ${displaystyle s}$ emas k-avtomatik. Evristik jihatdan, bitimdagi shartlarni tekshirib, avtomatiklikni isbotlashga urinish mumkin k-kernel, ammo bu ba'zida noto'g'ri taxminlarga olib kelishi mumkin. Masalan, ruxsat bering

${displaystyle t = 011010011dots}$

Thue-Morse so'zi bo'ling. Ruxsat bering ${displaystyle s}$ ning uzunlik qatoridagi ketma-ket atamalarni biriktirish orqali berilgan so'z bo'ling ${displaystyle t}$. Keyin ${displaystyle s}$ boshlanadi

${displaystyle s = 12112221dots.}$.

Ma'lumki ${displaystyle s}$ belgilangan nuqta ${displaystyle h ^ {omega} (1)}$ morfizmning

${displaystyle h (1) = 121, h (2) = 12221.}$

So'z ${displaystyle s}$ 2 avtomatik emas, lekin uning 2 yadrosining ba'zi elementlari ko'p shartlarga mos keladi. Masalan,${displaystyle s_ {16n + 1} = s_ {64n + 1} {ext {for}} 0leq nleq 1864134}$

lekin uchun emas ${displaystyle n = 1864135}$.^[30]

Avtomatik deb taxmin qilingan ketma-ketlikni hisobga olgan holda, uni isbotlash uchun bir nechta foydali yondashuvlar mavjud. Bitta yondashuv - ketma-ketlikni beradigan chiqim bilan to'g'ridan-to'g'ri deterministik avtomat qurish. Ruxsat bering ${displaystyle (s_ {n}) _ {ngeq 0}}$ alifboda yozilgan ${displaystyle Delta}$va ruxsat bering ${displaystyle (n) _ {k}}$ bazani belgilash-${displaystyle k}$ kengayishi ${displaystyle n}$. Keyin ketma-ketlik ${displaystyle s = (s_ {n}) _ {ngeq 0}}$ bu ${displaystyle k}$- avtomatik va faqat har bir tolalar

${displaystyle I_ {k} (s, d): = {(n) _ {k} o'rtadagi s_ {n} = d}}$

oddiy til.^[31] Elyaflarning muntazamligini tekshirish ko'pincha yordamida amalga oshirilishi mumkin oddiy tillar uchun nasosli lemma.

Agar ${displaystyle s_ {k} (n)}$ bazadagi raqamlar yig'indisini bildiradi-${displaystyle k}$ kengayishi ${displaystyle n}$ va ${displaystyle p (X)}$ manfiy bo'lmagan tamsayı koeffitsientlari bo'lgan polinom hisoblanadi va agar ${displaystyle kgeq 2}$, ${displaystyle mgeq 1}$ butun sonlar, keyin ketma-ketlik

${displaystyle (s_ {k} (p (n)) {pmod {m}}) _ {ngeq 0}}$

bu ${displaystyle k}$-avtomatik va agar shunday bo'lsa ${displaystyle deg pleq 1}$ yoki ${displaystyle mmid k-1}$.^[32]

1-avtomatik ketma-ketliklar

k-avtomatik ketma-ketliklar odatda faqat uchun belgilanadi k ≥ 2.^[1] Kontseptsiyani kengaytirish mumkin k = 1, 1-avtomatik ketma-ketlikni kimning ketma-ketligi bo'lishini aniqlash orqali n- muddat bog'liq unary notation uchun n; ya'ni (1)ⁿ. Cheklangan holatdagi avtomat oxir-oqibat ilgari tashrif buyurgan holatga qaytishi kerakligi sababli, barcha 1 ta avtomatik ketma-ketliklar oxir-oqibat davriydir.

Umumlashtirish

Avtomatik ketma-ketliklar ta'rifga yoki kirish ketma-ketligiga qarab o'zgaradi. Masalan, avtomat-nazariy ta'rifda ta'kidlanganidek, kirish ketma-ketligini to'g'ridan-to'g'ri va teskari o'qish paytida berilgan ketma-ketlik avtomatik bo'lib qoladi. Muqobil raqamlar to'plamidan foydalanilganda yoki bazani inkor etganda ketma-ketlik avtomatik ravishda qoladi; ya'ni kirish ketma-ketligi bazada ifodalanganida -k tayanch o'rniga k.^[33] Biroq, muqobil raqamlar to'plamidan farqli o'laroq, bazaning o'zgarishi ketma-ketlikning avtomatikligiga ta'sir qilishi mumkin.

Avtomatik ketma-ketlik domeni orqali natural sonlardan butun sonlarga kengaytirilishi mumkin ikki tomonlama avtomatik ketma-ketliklar. Bu berilganidan kelib chiqadi k ≥ 2, har bir butun son shaklida noyob tarzda ifodalanishi mumkin ${displaystyle sum _ {0leq ileq r} a_ {i} (- k) ^ {i},}$ qayerda ${displaystyle a_ {i} {0, nuqta, k-1}}$. Keyin ikki tomonlama cheksiz ketma-ketlik a(n)_{n ${displaystyle in mathbb {Z}}$} bu (-k) -avtomatik va faqat uning ketma-ketliklari bo'lsa a(n)_n-0 va a(−n)_n-0 bor k-avtomatik.^[34]

A alifbosi k-avtomatik ketma-ketlikni cheklangan kattalikdan cheksiz kattalikka kengaytirish mumkin k- muntazam ketma-ketliklar.^[35] The k-tartibli ketma-ketliklar kimning ketma-ketligi deb ta'riflanishi mumkin k-kernel nihoyatda hosil bo'ladi. Har bir cheklangan k- muntazam ketma-ketlik avtomatik.^[36]

Mantiqiy yondashuv

Ko'pgina 2 ta avtomatik ketma-ketliklar uchun ${displaystyle s = (s_ {n}) _ {ngeq 0}}$, xarita ${displaystyle nmapsto s_ {n}}$ birinchi darajali nazariya xususiyatiga ega ${displaystyle {ext {FO}} (mathbb {N}, +, 0,1, nmapsto s_ {n})}$ bu hal qiluvchi. Avtomatik ketma-ketliklarning ahamiyatsiz xususiyatlarini birinchi darajali mantiq bilan yozish mumkin bo'lganligi sababli, qaror qabul qilish protsedurasini bajarish orqali ushbu xususiyatlarni mexanik ravishda isbotlash mumkin.^[37]

Masalan, Thue-Morse so'zining quyidagi xususiyatlarini mexanik ravishda shu tarzda tekshirish mumkin:

• Thue-Morse so'zi bir-birining ustiga chiqmaydi, ya'ni tarkibidagi so'zni o'z ichiga olmaydi ${displaystyle cxcxc}$ qayerda ${displaystyle c}$ bitta harf va ${displaystyle w}$ ehtimol bo'sh so'z.
• Bo'sh bo'lmagan so'z ${displaystyle x}$ bu chegaradosh agar bo'sh bo'lmagan so'z bo'lsa ${displaystyle w}$ va ehtimol bo'sh so'z ${displaystyle y}$ bilan ${displaystyle x = wyw}$. Thue-Morse so'zida har bir uzunlik uchun chegaralangan koeffitsient 1 dan katta.^[38]
• Uzunlikning chegaralanmagan omili mavjud ${displaystyle n}$ Thue – Morse so'zida, agar shunday bo'lsa ${displaystyle (n) _ {2} otin 1 (01 ^ {*} 0) ^ {*} 10 ^ {*} 1}$ qayerda ${displaystyle (n) _ {2}}$ ning ikkilik vakilligini bildiradi ${displaystyle n}$.^[39]

Yong'oq dasturiy ta'minoti,^[40][41] Hamoon Musavi tomonidan ishlab chiqilgan, Thue-Morse so'zi kabi ba'zi bir avtomatik so'zlarning ko'plab xususiyatlarini qaror qilish tartibini amalga oshiradi. Ushbu dastur avtomatik ketma-ketliklarga mantiqiy yondoshish bo'yicha yuqoridagi ishlarning natijasidir.

Shuningdek qarang

• Büchi arifmetikasi

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.
• Berstel, Jan; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franko V. (2009). So'zlar bo'yicha kombinatorika. Christoffel so'zlari va takroriy so'zlar. CRM monografiya seriyasi. 27. Providence, RI: Amerika matematik jamiyati. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
• Berstel, Jan; Reutenauer, Christophe (2011). Ilovalar bilan birgalikda bo'lmagan ratsional qatorlar. Matematika entsiklopediyasi va uning qo'llanilishi. 137. Kembrij: Kembrij universiteti matbuoti. ISBN  978-0-521-19022-0. Zbl  1250.68007.
• Kobxem, Alan (1972). "Yagona yorliqlar ketma-ketligi". Matematika. Tizimlar nazariyasi. 6 (1–2): 164–192. doi:10.1007 / BF01706087.
• Lotari, M. (2005). So'zlar bo'yicha qo'llaniladigan kombinatorika. Matematika entsiklopediyasi va uning qo'llanilishi. 105. Jan Berstel, Dominik Perrin, Maksim Kroxemor, Erik Laport, Mehryar Mohri, Nadiya Pisanti, Mari-Frans Sagot, Gesine Reinert, Sofi Shbat, Maykl Voterman, Filipp Jak, Voytsex Shpankovski, Dominik Poulxon, Gill Sheffer, Roman Kolpakov, Gregori Kucherov, Jan-Pol Alloush va Valeri Berthe. Kembrij: Kembrij universiteti matbuoti. ISBN  978-0-521-84802-2. Zbl  1133.68067.
• Pytheas Fogg, N. (2002). Dinamikada, arifmetikada va kombinatorikada almashtirishlar. Matematikadan ma'ruza matnlari. 1794. Tahrirlovchilar Berti, Valeri; Ferentszi, Sebastyan; Modviy, nasroniy; Siegel, A. Berlin: Springer-Verlag. ISBN  978-3-540-44141-0. Zbl  1014.11015.

Qo'shimcha o'qish

• Berte, Valeri; Rigo, Mishel, nashr. (2010). Kombinatorika, avtomatika va raqamlar nazariyasi. Matematika entsiklopediyasi va uning qo'llanilishi. 135. Kembrij: Kembrij universiteti matbuoti. ISBN  978-0-521-51597-9. Zbl  1197.68006.
• Loxton, J. H. (1988). "13. Avtomatika va transsendensiya". Yilda Beyker, A. (tahrir). Transsendensiya nazariyasining yangi yutuqlari. Kembrij universiteti matbuoti. pp.215 –228. ISBN  978-0-521-33545-4. Zbl  0656.10032.
• Rowland, Erik (2015), "... avtomatik ketma-ketlik nima?", Amerika Matematik Jamiyati to'g'risida bildirishnomalar, 62 (3): 274–276, doi:10.1090 / noti1218.
• Shallit, Jefri (1999). "Raqamlar nazariyasi va rasmiy tillar". Yilda Hejhal, Dennis A.; Fridman, Joel; Gutzviller, Martin S; Odlyzko, Endryu M. (tahr.). Raqamlar nazariyasining paydo bo'layotgan dasturlari. IMA yozgi dasturi asosida, Minneapolis, MN, AQSh, 1996 yil 15-26 iyul. Matematika bo'yicha IMA hajmi va uning qo'llanilishi. 109. Springer-Verlag. 547-570 betlar. ISBN  978-0-387-98824-5.