Zapis łańcuchowy strzałek Conwaya

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

„Ł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 usnąć

Przykłady

Rozważmy teraz trzy przykłady:

zobacz liczba Grahama

Funkcja CG

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

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

gdzie przyjmuje formę

Wyrażenia typu: dla nie istnieją.

Przypisy

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