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, 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 $n+1$

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. $a\to b=a^{b}$
2. $a\to b\to c=a\underbrace {\uparrow \ldots \uparrow } _{c}b$
3. $a\to \ldots \to b\to 1=a\to \ldots \to b,$ jeśli ostatnim elementem jest 1, można ją usunąć
4. $a\to \ldots \to b\to 1\to c=a\to \ldots \to b,$ całą sekwencję po jedynce można usunąć
5. $a\to \ldots \to b\to c\to d=a\to \ldots \to b\to (a\to \ldots \to b\to (c-1)\to d)\to (d-1)$

Przykłady

Rozważmy teraz trzy przykłady:

$2\to 2\to 2\to 2=2\to 2\to (2\to 2\to 1\to 2)\to 1=2\to 2\to (2\to 2)\to 1=2\to 2\to 4\to 1=2\uparrow \uparrow \uparrow \uparrow 2=4$

$3\to 3\to 2=3\uparrow \uparrow 3=7.625.597.484.987$

$3\to 3\to 2\to 2=$

$=3\to 3\to (3\to 3\to 1\to 2)\to 1=$

$=3\to 3\to (3\to 3\to 1\to 2)=$

$=3\to 3\to (3\to 3)=$

$=3\to 3\to (3^{3})=$

$=3\to 3\to 27=$

$=3\uparrow ^{27}3>g(1),$ zobacz liczba Grahama

Funkcja CG

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

$cg(n)=\underbrace {n\to n\to \ldots \to n\to n} _{n},$ Funkcja daje wartości identyczne do liczb Ackermanna dla n od 1 do 3.

Wiadomo, że cg(4) $(4\to 4\to 4\to 4)$ jest znacznie większa od Liczby Grahama, która leży między $3\to 3\to 64\to 2,$ a $3\to 3\to 65\to 2.$

Dowód:

Najpierw zdefiniujmy funkcję: $f(n)=3\to 3\to n=3\underbrace {\uparrow \uparrow \ldots \uparrow \uparrow } _{n}3,$ która może być użyta do zdefiniowania liczby Grahama jako: $G=f^{64}(4),$ możemy więc rozposać:

$f^{64}(1)=3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3\to 1))\cdots )),$ z 64 $3\to 3.$

$=3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3)\to 1)\cdots )\to 1)\to 1$

$=3\to 3\to 64\to 2,$

$f^{64}(27)=3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3\to 27))\cdots ))$

$=3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3\to (3\to 3)))\cdots ))$

$=3\to 3\to 65\to 2$

Można więc stwierdzić, że liczba Grahama leży między $f^{64}(1),$ a $f^{64}(27).$

Rozszerzenia Petera Hurforda

Peter Hurford rozszerzył strzałki Cowaya o dodatkową zasadę:

$a\to _{c}b=\underbrace {a\to _{c-1}a\to _{c-1}\ldots \to _{c-1}a\to _{c-1}a} _{b\ \to _{c-1}},$ gdzie $\to$ przyjmuje formę $\to _{1}.$

Wyrażenia typu: $a\to _{b}c\to _{d}e,$ dla $b\neq d$ nie istnieją.