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

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