Przejdź do zawartości

Notacja strzałkowa

Z Wikipedii, wolnej encyklopedii

Notacja strzałkowa Knutha – metoda zapisywania bardzo dużych liczb wprowadzona przez amerykańskiego matematyka Donalda Knutha w 1976[1]. Podstawowa idea tej metody jest oparta na iterowanym potęgowaniu, w sposób podobny do tego jak potęgowanie jest iterowanym mnożeniem, mnożenie jest iterowanym dodawaniem, a dodawanie jest iterowaną inkrementacją. Celem tej notacji było zapisanie bardzo dużych liczb, których nawet zapisanie w postaci wykładniczej było trudne lub praktycznie niemożliwe do wykonania. Tempo wzrostu w szybko rosnącej hierarchii wynosi

Definicja

[edytuj | edytuj kod]

Z potęgowaniem jako podstawą:

dla wszystkich liczb całkowitych z

Dodatkowo w sekcji Inne przykłady wykazano, że:

Z mnożeniem jako podstawą[2]:

dla wszystkich nieujemnych liczb całkowitych

Dla otrzymamy zwykłe potęgowanie dla tetrację, dla pentację(inne języki) itd. (ang. n-hyperoperation(inne języki))[2].

Przykłady

[edytuj | edytuj kod]

Opis notacji

[edytuj | edytuj kod]

Dla skrócenia zapisu dużą ilość strzałek zastępuje się ich liczbą umieszczoną po prawej stronie strzałki w indeksie górnym:

Konstrukcja

[edytuj | edytuj kod]

gdzie występuje po prawej stronie równań zawsze dokładnie razy.

Inne przykłady

[edytuj | edytuj kod]
a stąd indukcyjnie uzasadniamy, że dla wszystkich
i stąd indukcyjnie uzasadniamy, że dla wszystkich

Liczba Grahama

[edytuj | edytuj kod]
 Osobny artykuł: Liczba Grahama.

Oznaczmy Wtedy itd. Liczbę nazywamy liczbą Grahama.

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  1. Eric W. Weisstein, Knuth Up-Arrow Notation, [w:] MathWorld, Wolfram Research [dostęp 2016-05-14] (ang.).
  2. a b Fabio Caldarola i inni, On the Arithmetic of Knuth’s Powers and Some Computational Results About Their Density, [w:] Yaroslav D. Sergeyev, Dmitri E. Kvasov, Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019, Revised Selected Papers, Part I, Springer Nature, 13 lutego 2020, s. 382, ISBN 978-3-030-39081-5 [dostęp 2023-03-08] (ang.).