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

${\displaystyle 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}$

${\displaystyle 3\to 3\to 2=3\uparrow \uparrow 3=7,625,597,484,987}$

${\displaystyle 3\to 3\to 2\to 2=}$

${\displaystyle =3\to 3\to (3\to 3\to 1\to 2)\to 1=}$

${\displaystyle =3\to 3\to (3\to 3\to 1\to 2)=}$

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

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

${\displaystyle =3\to 3\to 27=}$

${\displaystyle =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:

${\displaystyle 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) ${\displaystyle (4\to 4\to 4\to 4)}$ jest znacznie większa od Liczby Grahama, która leży między ${\displaystyle 3\to 3\to 64\to 2,}$ a ${\displaystyle 3\to 3\to 65\to 2.}$

Dowód:

Najpierw zdefiniujmy funkcję: ${\displaystyle 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: ${\displaystyle G=f^{64}(4),}$ możemy więc rozposać:

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

${\displaystyle =3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3)\to 1)\cdots )\to 1)\to 1}$

${\displaystyle =3\to 3\to 64\to 2,}$

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

${\displaystyle =3\to 3\to (3\to 3\to (\cdots (3\to 3\to (3\to 3\to (3\to 3)))\cdots ))}$

${\displaystyle =3\to 3\to 65\to 2}$

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

Rozszerzenia Petera Hurforda

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

${\displaystyle 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 ${\displaystyle \to }$ przyjmuje formę ${\displaystyle \to _{1}.}$

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

Przypisy