Knuthova iterovaná mocninová notace

V matematice je notace iterovaných sil Knutha notací, která umožňuje psát velmi velká celá čísla a kterou zavedl Donald Knuth v roce 1976. Myšlenka této notace je založena na konceptu opakované umocňování , v stejně jako umocňování sestává z iterovaného násobení nebo násobení iterovaného sčítání .

Úvod

Iterovat jednoduchou funkci

Iterace jednoduché funkce se používá v aritmetice k definování složitější operace. Z funkce nástupce , která umožňuje konstrukci přirozených celých čísel po sobě jdoucích přírůstcích , je tak přidání definováno jako iterovaná přírůstek:

{\ begin {matrix} a + b = a + \ underbrace {1 _ {{}} + 1+ \ dots +1} \\\ qquad \ quad \ \ b {\ mbox {výtisky}} 1 \ end { matice}}

Násobení je definováno jako iterovaný sčítání:

{\ begin {matrix} a \ times b = \ underbrace {a _ {{}} + a + \ dots + a} \\\ qquad \ quad \ \ b {\ mbox {kopie}} a \ end {matice }}

Podobně je umocňování definováno jako iterované násobení:

{\ begin {matrix} a ^ {b} = \ underbrace {a _ {{}} \ times a \ times \ dots \ times a} \\\ qquad \ b {\ mbox {kopie}} a \ end { matice}}

Zobecnění

Z přírůstku jako primitivní operace umožňují následné iterace definovat nejprve sčítání, poté násobení a potom umocňování. Knuth chtěl tento princip zobecnit; za tímto účelem zavedl novou notaci pro umocňování, šipku nahoru :

{\ displaystyle a \ uparrow b = a ^ {b}}

který může takto zobecnit pomocí dvojité šipky nahoru pro iterovanou umocňování - kterou nazývá tetrace :

{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow b = \ underbrace {a \ uparrow a \ uparrow \ cdots \ uparrow a} = a _ {} ^ {a ^ {{} ^ {. \, ^ { . \, ^ {. \, ^ {a}}}}}} \\\ \ \ b {\ mbox {kopie}} a \ end {matice}}}

V souladu s touto definicí získáváme:

3 \ uparrow \ uparrow 2 = 3 ^ {3} = 27 \, \!

{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 ^ {3 ^ {3}} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 \, \!}

{\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}} = 3 ^ {7 \, 625 \, 597 \, 484 \, 987} \, \!}

3 \ uparrow \ uparrow 5 = 3 ^ {{3 ^ {{3 ^ {{3 ^ {3}}}}}}} \, \!

atd.

Termín má formu a má číslice, tj. Více než desetinná místa. ${\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}}}$ ${\ displaystyle 12580 ... 39387}$ ${\ displaystyle 3 \, 638 \, 334 \, 640 \, 025}$ ${\ displaystyle 3,6 \ krát 10 ^ {12}}$

Určitě umožňuje psát velmi velká čísla, ale Knuth se tím nezastavil. Pokračoval definováním operátoru trojité šipky nahoru, což je iterovaná aplikace operátoru dvojité šipky nahoru :

{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {} \ uparrow \ uparrow a \ uparrow \ uparrow \ dots \ uparrow \ uparrow a} = a _ {} \ uparrow \ uparrow (a \ uparrow \ uparrow (\ dots \ uparrow \ uparrow a))) \\\ qquad \ qquad \ \, b {\ mbox {kopie}} a \ end {matice}}}

(operace prováděné zprava doleva)

pak pokračoval s operátorem čtyřnásobné šipky nahoru :

{\ begin {matrix} a \ uparrow \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {{}} \ uparrow \ uparrow \ uparrow a \ uparrow \ uparrow \ uparrow \ dots \ uparrow \ uparrow \ uparrow a} \ \ \ qquad \ qquad \ quad b {\ mbox {kopie}} a \ end {matice}}

A tak dále. Obecné pravidlo říká, že operátor n -arrow je posloupnost operátorů ( n - 1) -arrows. Obecněji, $b$ $b$

{\ begin {matrix} a \ \ underbrace {\ uparrow _ {{}} \ uparrow \! \! \ dots \! \! \ uparrow} \ b = a \ \ underbrace {\ uparrow \! \! \ dots \ ! \! \ uparrow} \ a \ \ underbrace {\ uparrow _ {{}} \! \! \ dots \! \! \ uparrow} \ a \ \ dots \ a \ \ underbrace {\ uparrow _ {{}} \! \! \ dots \! \! \ uparrow} \ a \\\ quad \ \ \, n \ qquad \ \ \ \ underbrace {\ quad n _ {{}} \! - \! \! 1 \ quad \ \, n \! - \! \! 1 \ qquad \ quad \ \ \ \, n \! - \! \! 1 \ \ \} \\\ qquad \ qquad \ quad \ \ b {\ mbox {kopie of}} a \ end {matrix}}

Komutativita

Vyjádření není komutativní : pokud se a a b liší, liší se od . Je to stejné pro provozovatele následujících: , , atd. ${\ displaystyle a \ uparrow b}$ ${\ displaystyle b \ uparrow a}$ $\ šipka nahoru$ ${\ displaystyle \ uparrow \ uparrow}$ ${\ displaystyle \ uparrow \ uparrow \ uparrow}$

Závorky a asociativita

Ačkoli žádná závorka je psáno, výpočty spojené přednostní právo pro každého provozovatele , , atd $\ šipka nahoru$ ${\ displaystyle \ uparrow \ uparrow}$ ${\ displaystyle \ uparrow \ uparrow \ uparrow}$

Příklad: = ${\ displaystyle 3 \ uparrow 2 \ uparrow \ uparrow 3 \ uparrow 4}$ ${\ displaystyle 3 \ uparrow (2 \ uparrow \ uparrow (3 \ uparrow 4)))}$

Je to proto, že umocňování není asociativní , proto je důležité pořadí, ve kterém jsou operace prováděny. Takže (tj. ) Není (tj. ). Ve výše uvedeném jsou operace prováděny zprava doleva, jinými slovy, závorky jsou spojeny zprava doleva. ${\ displaystyle 3 \ uparrow (2 \ uparrow 3)}$ ${\ displaystyle 3 \ uparrow 8 = 6 \, 561}$ ${\ displaystyle (3 \ uparrow 2) \ uparrow 3}$ ${\ displaystyle 9 \ uparrow 3 = 729}$

Všimněte si, že na základě pravidel moci dostaneme = = . Pokud by si někdo vybral prioritní sdružení vlevo, přivedlo by to druhého energetického operátora zpět k „jednoduché“ multiplikační operaci. Růst moci je silnější, když zvětšíme člen vpravo (to je u původu nekomutativity): ${\ displaystyle (3 \ uparrow 2) \ uparrow 3}$ ${\ displaystyle (3 \ uparrow 2) \ krát (3 \ uparrow 2) \ krát (3 \ uparrow 2)}$ ${\ displaystyle 3 \ uparrow (2 \ krát 3)}$

${\ displaystyle 3 \ uparrow (2 \ uparrow 3)}$ = = je větší než = = . ${\ displaystyle 3 \ uparrow (2 \ krát 2 \ krát 2)}$ ${\ displaystyle 3 \ uparrow 8}$ ${\ displaystyle (3 \ uparrow 2) \ uparrow 3}$ ${\ displaystyle (3 \ krát 3) \ uparrow 3}$ ${\ displaystyle 9 \ uparrow 3}$

Sdružení je proto vybráno jako priorita vpravo; je to jediná volba, která produkuje růst hodný nového operativního znamení.
Výsledek bude tedy 6 561 a ne 729. ${\ displaystyle 3 \ uparrow 2 \ uparrow 3}$

Definice iterovaných pravomocí

Knuthovy iterované síly jsou formálně definovány takto:

a \ uparrow ^ {n} b = \ left \ {{\ start {matrix} a ^ {b} \ qquad \ qquad \ qquad \ qquad && {\ mbox {si}} n = 1 \ quad \\ 1 \ qquad \ qquad \ qquad \ qquad \ && {\ mbox {si}} b = 0 \ quad \, \\ a \ uparrow ^ {{n-1}} (a \ uparrow ^ {n} (b-1)) && {\ mbox {jinak}} \ \, \ end {matrix}} \ vpravo.

pro všechna celá čísla a , b a n, kde b ≥ 0 a n ≥ 1.

Tuto rodinu funkcí lze definovat iteračním programem:

function Knuth(rang: naturel; a, b: naturel) : naturel begin if rang = 1 then R = a^b else begin R := 1 (* 1 est élément neutre à droite pour l'exponentiation *) (* Application b fois de l'opérateur à gauche "a Knuth(rang-1)" *) for compteur := 1 to b do R := Knuth(rang-1, a, R) end return R end.

nebo rekurzivním programem ( například v Haskellu ):

(↑) :: Integer -> (Integer, Integer) -> Integer a ↑ (1,b) = a^b _ ↑ (_,0) = 1 a ↑ (n,b) = a ↑ (n-1,a ↑ (n,b-1))

Poznámky ke skórování

Ve výrazu b , píšeme exponent b v horní části dopisu . Mnoho prostředí, jako jsou programovací jazyky a e - maily v prostém textu, však toto dvojrozměrné uspořádání nepodporuje. Navrhli proto lineární zápis, a ** b pro Fortran a a ↑ b pro jiná prostředí; šipka směřující nahoru naznačuje povýšení na sílu. Pokud znaková sada neobsahuje šipku, použije se háček ^ nebo obě hvězdičky ** .

Další notace použitá v tomto článku je ↑ n k označení operátoru šipky řádu n (kde ↑ 1 odpovídá ↑ samotnému).

Jak jsme řekli výše, všechny tyto operátory (včetně klasické umocňování a ↑ b ) nejsou asociativní a při absenci závorek musí být spojeny, zprava doleva, to znamená - to znamená, že hodnocení se provádí zprava doleva pro výraz, který obsahuje alespoň dva z těchto operátorů. Například a ↑ b ↑ c znamená a ↑ ( b ↑ c ), a nikoli ( a ↑ b ) ↑ c, které by pak bylo napsáno a ↑ ( b × c ):

{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 \ uparrow ^ {2} 3 = 3 ^ {3 ^ {3}} {\ mbox {má hodnotu}} 3 ^ {(3 ^ {3})} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 {\ text {a ne}} \ vlevo (3 ^ {3} \ vpravo) ^ {3} = 27 ^ {3} = 3 ^ { (3 \ cdot 3)} = 3 ^ {9} = 19 \, 683.}

Je dobrý důvod zvolit si toto hodnocení zprava doleva; Skutečně, pokud by byl výběr zleva doprava, pak ↑↑ b by znamenalo ↑ ( ↑ ( b -1)) a ↑↑ by nebyl nový operátor.

Zevšeobecnění Knuthovy notace

Některá čísla jsou tak velká, že Knuthova šípová notace je příliš těžkopádná na to, aby je popsala. To je například případ Grahamova čísla . Tyto hyperopérateurs nebo zřetězené šipka Conway pak mohou být použity.

{\ begin {matrix} a \ uparrow ^ {n} b && = && {\ mbox {hyper}} (a, n + 2, b) && = && a \ to b \ to n \\ {\ mbox {( Knuth)}} &&&&&&&& {\ mbox {(Conway)}} \ end {matrix}}

Knuthova šipka bude použita pro malá čísla vzhledem k těmto, zatímco zřetězené šipky nebo hyperoperátoři budou vhodné pro větší; když se tyto notace samy stanou nedostatečnými, jako je tomu například u Goodsteinových sekvencí , je stále možné použít hierarchii rychlého růstu (což je zhruba ekvivalent definování notace , kde α je pořadové číslo ). ${\ displaystyle a \ uparrow ^ {\ alpha} b}$

Reference

přírůstek je proces přidávání číslo. Například v zápisu celých čísel domino (nebo malými oblázky) by to spočívalo v přidání domina (nebo oblázku). $1$
Pokračování A014222 v online encyklopedii celočíselných řetězců .
Vynecháváme kvalifikátor „nahoru“.
„Horní písmeno“ je termín používaný v typografii.

Bibliografie

(en) Knuth, Donald E., „ Mathematics and Computer Science: Coping with Finiteness “ , Science , sv. 194, n O 4271,1976, str. 1235–1242 ( PMID 17797067 , DOI 10.1126 / science.194.4271.1235 )

externí odkazy

Na blogu o Mickaël Launay