Hofštatera Q-rinda
Lēnām un neatlaidīgi turpinu lasīt Duglasa Hofštatera "Goedel, Escher, Bach: an Eternal Golden Braid". Lai arī visticamākais ar šo grāmatu galā netikšu vēl vismaz dažus mēnešus, tā varētu pretendēt uz tādas grāmatas statusu, kas uz mani atstājusi vislielāko iespaidu pēdējo n gadu laikā. Tāpēc arī necenšos to pievarēt pārāk ātri, jo kāda gan jēga ir pārmērīgi ātri pārskriet pāri grāmatai, kas tevi motivē uz domāšanu un dod iedvesmu un idejas. Tieši šīs grāmatas iespaidā uzrakstīju savus divus pēdējos stāstus - Mana pēdējā dziesma un Dusmas against the Machine. Protams, ka ne jau tieši no grāmatas ietekmējos, bet tā kalpoja par idejisku atspēriena punktu. Un ja būtu man pacietība realizēt citas idejas, šādu stāstu būtu vairāk. Turklāt tieši šī grāmata man radīja domu, ka varbūt vajadzētu atsākt studijas. Pēdējais punkts gan ir zem milzīgas jautājuma zīmes - bet ko var zināt, varbūt tomēr kādreiz...
It kā jau nekādas mega sarežģītās lietas šajā grāmatā nav - citādi diez vai Hofštaters par to varētu dabūt Pulicera balvu, bet viņam patiešām ir satriecošas spējas tēmu pasniegt tā, lai man tas šķistu interesanti.
Šodien lasu par rekursiju. Droši vien katrs pirmā kursa datorikas (matemātikas) students un vismaz sava tiesa vidusskolnieku ir pazīstami ar Fibonači skaitļiem - 1 1 2 3 5 7 12 utt. Ja nemaldos, pat Dens Brauns "Da Vinči" kodā to izmantoja (varbūt arī maldos, bet tas nav būtiski).
Hofštaters savā grāmatā piedāvā līdzīgu virknes definīciju, tā saukto Hofštatera Q-rindu, ko definē šādi:
a(1) = a(2) = 1; a(n)=a(n-a(n-1))+a(n-a(n-2)) for n > 2
Programma, kas rēķina k-to virknes skaitli, uzrakstāma sekunžu laikā un bez jebkādām problēmām. Taču pati skaitļu virkne ir daudz pārsteidzošāka par Fibonači virkni. Pirmie skaitļi tajā ir sekojoši:
1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 12 12 12 16 14 14 16 16 16 16 20
Sākums vēl būtu ok - bet no brīža 10 - 9 - 10 sāk jau kļūt nedaudz dīvaināk. Un tālāk funkcija kļūst arvien haotiskāka un haotiskāka.
Grafiski tas izskatās šādi:
(attēls no AT&T Integer Sequences Research)
Interesantums te ir tajā, ka par šīs virknes īpašībām ir zināms diezgan maz - it kā tā šķiet haotiska, bet likumsakarības tajā ir atrodamas, un nav arī zināms, vai Q-rinda ir definēta visiem naturāliem skaitļiem, vai arī pastāv kāds līmenis, kurā tās nobīdes noved pie sabrukuma.