Zapis łańcuchowy strzałek Conwaya – Wikipedia, wolna encyklopedia

Zapis łańcuchowy strzałek Conwaya (również notacja łańcuchowa Conwaya), stworzona przez matematyka Johna Hortona Conwaya i Richarda Kennetha Guya[1], jest sposobem wyrażania pewnych dużych liczb. Składa się ze skończonej sekwencji dodatnich liczb całkowitych oddzielonych przez strzałkę w prawo, np. 4 → 5 → 6 → 7 → 9.

Jak w przypadku większości notacji kombinatorycznych, definicja jest rekursywna.

Definicja

[edytuj | edytuj kod]

„Łańcuch Conwaya” jest zdefiniowany następująco:

  1. Każda dodatnia liczba całkowita jest łańcuchem o długości 1.
  2. Łańcuch o dowolnej długości n, po którym następuje znak strzałki (→) i dowolna liczba całkowita, razem tworzy łańcuch o długości

Każdy łańcuch reprezentuje liczbę całkowitą, zgodnie z czterema zasadami poniżej. Mówimy, że łańcuchy są równoważne, jeśli reprezentują tę samą liczbę.

  1. jeśli ostatnim elementem jest 1, można ją usunąć
  2. całą sekwencję po jedynce można usunąć

Przykłady

[edytuj | edytuj kod]

Rozważmy teraz trzy przykłady:

zobacz liczba Grahama

Funkcja CG

[edytuj | edytuj kod]

Używając notacji łańcuchowej, Conway i Guy stworzyli nową funkcję podobną do funkcji Ackermanna. Oto jej definicja:

Funkcja daje wartości identyczne do liczb Ackermanna dla n od 1 do 3.

Wiadomo, że cg(4) jest znacznie większa od Liczby Grahama, która leży między a

Dowód:

Najpierw zdefiniujmy funkcję: która może być użyta do zdefiniowania liczby Grahama jako: możemy więc rozposać:

z 64

Można więc stwierdzić, że liczba Grahama leży między a

Rozszerzenia Petera Hurforda

[edytuj | edytuj kod]

Peter Hurford rozszerzył strzałki Cowaya o dodatkową zasadę[2][3]:

gdzie przyjmuje formę

Wyrażenia typu: dla nie istnieją.

Przypisy

[edytuj | edytuj kod]
  1. J.H. Conway i R.K. Guy, The Book of Numbers.
  2. Large Numbers, Part 2: Graham and Conway - Greatplay.net [online], archive.vn, 25 czerwca 2013 [dostęp 2020-04-14].
  3. Large Numbers, Part 3: Functions and Ordinals - Greatplay.net [online], archive.vn, 25 czerwca 2013 [dostęp 2020-04-14].