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:
- Każda dodatnia liczba całkowita jest łańcuchem o długości 1.
- Ł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ę.
- jeśli ostatnim elementem jest 1, można ją usunąć
- całą sekwencję po jedynce można usunąć
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
- ↑ J.H. Conway i R.K. Guy , The Book of Numbers .
- ↑ Large Numbers, Part 2: Graham and Conway - Greatplay.net [online], archive.vn, 25 czerwca 2013 [dostęp 2020-04-14] .
- ↑ Large Numbers, Part 3: Functions and Ordinals - Greatplay.net [online], archive.vn, 25 czerwca 2013 [dostęp 2020-04-14] .