Hofstadter sorozat

A Hofstadter sorozat a nemlineáris ismétlődő képletek által meghatározott egész sorozatok családjának egyike .

Sorozatok Gödeltől, Eschertől, Bachtól: ez a végtelen füzér

Az első Hofstadter-szekvenciákat Douglas Hofstadter írta le Gödel, Escher, Bach című könyvében . A szekvenciákat bemutatásuk sorrendjében az ábrákkal és háttérrel foglalkozó III. fejezetben (ábra-ábra sorozat), valamint a rekurzív struktúrákról és folyamatokról szóló V. fejezetben (egyéb sorozatok) mutatjuk be.

Hofstadter rajz-rajz sorozatai

A Hofstadter Drawing-Drawing sorozatok ( R és S ) komplementer egész sorozatok párja . Az { R } szekvencia meghatározása a következő: [1] [2]

és az {S( n )} sorozat az {R( n )} -ban nem szereplő pozitív egészek szigorúan növekvő sorozata . Ezeknek a sorozatoknak az első néhány tagja

R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... ( OEIS8 szekvencia A05 ) S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... ( OEIS szekvencia A030124 )

Hofstadter G-szekvenciája

A G Hofstadter-szekvencia meghatározása a következő: [3] [4]

Ennek a sorozatnak az első néhány tagja

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... ( OEIS szekvencia A005206 )

A Hofstadter sorozat H

A H Hofstadter-szekvencia meghatározása a következő: [3] [5]

Ennek a sorozatnak az első néhány tagja

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... ( OEIS szekvencia A005374 )

Hofstadter női és férfi sorozatai

A női (F) és férfi (M) Hofstadter szekvenciákat a következőképpen határozzuk meg [3] [6]

Ezeknek a sorozatoknak az első néhány tagja

F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... ( A005378 sorozat az OEIS -ben ) M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... ( A005379 sorozat az OEIS -ben )

Hofstadter Q sorozata

A Q Hofstadter-szekvencia a következőképpen definiálható [3] [7] :

Ennek a sorozatnak az első néhány tagja

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... ( A005185 sorozat az OEIS -ben )

Hofstadter a sorozat tagjait "Q-számoknak" nevezte [3] . Így a Q 6. száma 4. A Q szekvencia Hofstadter könyvében való ábrázolása valójában a Fibonacci metaszekvenciák első említése a szakirodalomban [8] .

Míg a Fibonacci-számokat az előző két tag összegzésével határozzuk meg, addig a Q sorozat előző két tagja határozza meg, hogy meddig kell visszamenni ahhoz, hogy a sorozat tagjait összegezzük. Az összegzés indexeit ugyanazzal a Q sorozattal adjuk meg.

Q(1), a sorozat első eleme, csak a Q(3) kiszámítására szolgál [9] .

Bár a Q szekvencia kaotikusnak tűnik [3] [10] [11] [12] , sok más Fibonacci metaszekvenciához hasonlóan tagjai blokkokba csoportosíthatók [13] [14] . A Q sorozatnál a k - edik blokk 2 k tagú [15] . Ráadásul a Q-számhoz tartozó blokkhoz tartozó g esetében a Q-szám kiszámításához használt két kifejezés, amelyet szülőknek nevezünk, többnyire a g  − 1 blokkban található, és csak néhány tag van a g  − blokkban. 2, de a korábbi blokkokban soha [16] .

Ezeknek az eredményeknek a többsége empirikus megfigyelés, mivel a Q -szekvenciával kapcsolatban a mai napig semmit sem bizonyítottak szigorúan [17] [18] [19] . Különösen nem ismert, hogy a szekvencia jól definiált-e minden n esetén . Ez azt jelenti, hogy a szekvencia "elhal-e" valamikor azáltal, hogy megpróbálja használni a Q(1) első tagjától balra lévő sorozattagot. [12] [17] [19]


Egy példa az algoritmus megértéséhez:

például be kell cserélni a Q(1) = 1, Q(2)=1 értékeket (feltétel szerint).

Q(3) = Q(3-1)+Q(3-1) = Q(2)+ Q(2) = 2

Q(4) = (Q(4-Q(3))+Q(4-Q(2)) = Q(4-2)+Q(4-1) = Q(2)+Q(3) = 1+2=3

A Q sorozat általánosításai

A Hofstadter–Huber család Q r , s ( n )

20 évvel azután, hogy Hofstadter leírta a Q szekvenciát, Hofstadter és Greg Huber a Q szimbólumot használta a Q szekvencia általánosítására szekvenciacsaládra, és az eredeti Q szekvenciát átnevezték U szekvenciára [19] .

Az eredeti Q sorozatot úgy általánosítjuk, hogy ( n  − 1) és ( n  − 2) helyére ( n  −  r ) és ( n  −  s ) cseréljük [19] .

Ennek eredménye egy sorozat sorozata

ahol s  ≥ 2 és r  <  s .

Az ( r , s ) = (1,2) esetén megkapjuk az eredeti Q sorozatot , tehát ennek a családnak a tagja. Jelenleg a Q r , s családnak csak három sorozata ismert , mégpedig az U sorozat ( r , s ) = (1,2) (az eredeti Q sorozat ) [19] , a V sorozat ( r , s ) ) = (1 ,4) [20] és egy W sorozat , ahol (r,s) = (2,4) [19] . Csak az V szekvencia esetében, amely nem viselkedik olyan kaotikusan, mint a másik kettő, bebizonyosodott, hogy nem "hal meg" [19] . Az eredeti Q szekvenciához hasonlóan a W sorozatra sem sikerült semmit sem bizonyítani [19] .

Az V sorozat néhány első tagja

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... ( OEIS szekvencia A063882 )

A W sorozat néhány első tagja

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... ( OEIS szekvencia A087777 )

Más értékeknél ( r , s ) a sorozatok előbb-utóbb "elhalnak", pl. létezik n , amelyre Q értéker , s ( n ) nem definiált, mert n  −  Qr , s ( n  −  r ) < 1 [19] .

F i , j ( n ) sorozatok családja

1998-ban Klaus Pinn, a Münsteri Egyetem (Németország) tudósa, szoros kapcsolatban Hofstadterrel, a Hofstadter Q -szekvenciájának egy újabb általánosítását javasolta , és a kapott szekvenciákat F - szekvenciáknak nevezte [21] .

Az F i , j Pinn sorozatok családját a következőképpen definiáljuk:

Így Pinn további i és j állandókat vezetett be , amelyek az összegzett tagok indexeit balra (vagyis közelebb a sorozat elejéhez) tolják el [21] .

Csak az ( i , j ) = (0,0), (0,1), (1,0) és (1,1) F sorozatok bizonyulnak jól, amelyek közül az első az eredeti Q sorozat. meghatározott [21] . Q (1)-től eltérően az F i , j ( n ) Pinn sorozatok első elemei a sorozat többi elemének kiszámítására szolgálnak, ha a további állandók egyike 1.

A sorozat első néhány tagja F 0.1 Pinn

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... OEIS sorozat A046699

10 000 dollár Hofstadter-Conway sorozat

A 10 000 dolláros Hofstadter-Conway sorozatot a következőképpen határozzuk meg [22]

A sorozat első néhány tagja

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … ( A004001 sorozat az OEIS -ben )

A sorozat azért kapta a nevét, mert John Horton Conway 10 000 dolláros bónuszt hirdetett mindenkinek, aki bizonyos eredményt tud felmutatni a sorozat aszimptotikus viselkedésével kapcsolatban. Az 1000 dollárra csökkentett díjat Collin Mallows kapta [23] . A Klaus Pinnnel folytatott privát beszélgetés során Hofstadter később azt állította, hogy a sorozatot és annak szerkezetét körülbelül 10-15 évvel Conway díj bejelentése előtt találta meg [10] .

Jegyzetek

  1. ↑ Hofstadter, 1980 , p. 73.
  2. ↑ Weisstein, Eric W. Hofstadter ábra-ábra sorozat  a Wolfram MathWorld webhelyen .
  3. ↑ 1 2 3 4 5 6 Hofstadter, 1980 , p. 137.
  4. ↑ Weisstein, Eric W. Hofstadter G-Sequence  a Wolfram MathWorld webhelyén .
  5. ↑ Weisstein, Eric W. Hofstadter H-Sequence  a Wolfram MathWorld webhelyén .
  6. ↑ Weisstein, Eric W. Hofstadter férfi-nő szekvenciák  a Wolfram MathWorld webhelyen .
  7. ↑ Weisstein, Eric W. Hofstadter Q-Sequence  a Wolfram MathWorld webhelyén .
  8. ↑ Emerson, 2006 , p. 1, 7.
  9. ↑ Pinn, 1999 , p. 5–6.
  10. ↑ Pinn 12. , 1999. , p. 3.
  11. ↑ Pinn, 2000 , p. egy.
  12. ↑ 12. Emerson , 2006 , p. 7.
  13. ↑ Pinn, 1999 , p. 3–4.
  14. ↑ Balamohan, Kuznyecov, Tanny, 2007 , p. 19.
  15. ↑ Pinn, 1999 , p. absztrakt, 8.
  16. ↑ Pinn, 1999 , p. 4–5.
  17. ↑ Pinn 12. , 1999. , p. 2.
  18. ↑ Pinn, 2000 , p. 3.
  19. ↑ 1 2 3 4 5 6 7 8 9 Balamohan, Kuznetsov, Tanny, 2007 , p. 2.
  20. ↑ Balamohan, Kuznyecov, Tanny, 2007 .
  21. ↑ 1 2 3 Pinn, 2000 , p. 16.
  22. ↑ Weisstein, Eric W. Hofstadter-Conway 10 000 dolláros sorozat  a Wolfram MathWorld webhelyén .
  23. ↑ Tempel .

Irodalom