Конвейдің тізбекті тізбегі - Conway chained arrow notation

Конвейдің тізбекті тізбегі, математик жасаған Джон Хортон Конвей, белгілі бір шекті білдіру құралы болып табылады үлкен сандар.^[1] Бұл жай шектеулер тізбегі натурал сандар оңға бағытталған көрсеткілермен бөлінген, мысалы. ${ displaystyle 2 to 3 to 4 to 5 to 6} дейін$.

Көпшілігінде сияқты комбинаторлық белгілері, анықтамасы рекурсивті. Бұл жағдайда жазба ақыр соңында бүтін қуатқа дейін көбейтілетін сол жақтағы санға айналады.

Анықтама және шолу

«Конвей тізбегі» келесідей анықталады:

• Кез келген натурал сан - ұзындық тізбегі ${ displaystyle 1}$.
• Ұзындық тізбегі n, содан кейін оң жақ көрсеткі → және оң бүтін сан, бірге ұзындық тізбегін құрайды ${ displaystyle n + 1}$.

Төмендегі бес (техникалық төрт) ережеге сәйкес кез-келген тізбек бүтін санды білдіреді. Екі тізбек бірдей бүтін санды көрсетсе, балама деп аталады.

Егер ${ displaystyle p}$, ${ displaystyle q}$, және ${ displaystyle r}$ натурал сандар, және ${ displaystyle X}$ қосалқы тізбек, содан кейін:

1. Бос тізбек (немесе ұзындығы 0 тізбек) тең ${ displaystyle 1}$және тізбек ${ displaystyle p}$ санды білдіреді ${ displaystyle p}$.
2. ${ displaystyle X to 1}$ дегенге тең ${ displaystyle X}$.
3. ${ displaystyle p rightarrow q rightarrow r}$ дегенге тең ${ displaystyle p [ uparrow ^ {r}] q}$. (қараңыз Кнуттың жоғары көрсеткі )
4. ${ displaystyle X to p to (q + 1)}$ дегенге тең ${ displaystyle X to (X to ( cdots (X to (X) to q) cdots) to q) to q}$
   (бірге ${ displaystyle p}$ дана ${ displaystyle X}$, ${ displaystyle p-1}$ дана ${ displaystyle q}$, және ${ displaystyle p-1}$ жақшалар; үшін қолданылады ${ displaystyle q}$ > 0).
5. Себебі ${ displaystyle p rightarrow q rightarrow 1}$ дегенге тең ${ displaystyle p to q}$, (2 ереже бойынша) және сонымен бірге ${ displaystyle p uparrow q}$ = ${ displaystyle p ^ {q}}$, (3 ереже бойынша) біз анықтай аламыз ${ displaystyle p to q}$ тең ${ displaystyle p ^ {q}}$

Төртінші ережені келесі ережелерді болдырмау үшін бірнеше ережелерді қолданумен ауыстыруға болатындығын ескеріңіз эллипс:

4а. ${ displaystyle X to 1 to (q + 1)} дейін$ дегенге тең ${ displaystyle X}$

4b. ${ displaystyle X to (p + 1) to (q + 1)}$ дегенге тең ${ displaystyle X to (X to p to (q + 1)) to q}$

Қасиеттері

1. Тізбек өзінің алғашқы санының керемет күшіне баға береді
2. Сондықтан, ${ displaystyle 1 бастап Y}$ тең ${ displaystyle 1}$
3. ${ displaystyle X to 1 to Y} дейін$ дегенге тең ${ displaystyle X}$
4. ${ displaystyle 2 ден 2 дейін Y}$ тең ${ displaystyle 4}$
5. ${ displaystyle X to 2 to 2}$ дегенге тең ${ displaystyle X to (X)}$ (шатастыруға болмайды ${ displaystyle X to X}$)

Түсіндіру

Жебе тізбегіне мұқият қарау керек тұтастай алғанда. Жебелік тізбектер екілік оператордың қайталанатын қолданбасын сипаттамайды. Ал басқа жалғанған белгілердің тізбектерін (мысалы, 3 + 4 + 5 + 6 + 7) көбінесе фрагменттерде (мысалы, (3 + 4) + 5 + (6 + 7)) мағынасын өзгертусіз қарастыруға болады (қараңыз) ассоциативтілік ) немесе кем дегенде белгіленген тәртіппен кезең-кезеңмен бағалауға болады, мысалы. 3⁴⁵⁶⁷ оңнан солға қарай, бұл Конвейдің жебе тізбектерінде олай емес.

Мысалға:

• ${ displaystyle 2 rightarrow 3 rightarrow 2 = 2 uparrow uparrow 3 = 2 ^ {2 ^ {2}} = 16}$
• ${ displaystyle 2 rightarrow left (3 rightarrow 2 right) = 2 ^ {(3 ^ {2})} = 2 ^ {3 ^ {2}} = 512}$
• ${ displaystyle сол жақ (2 оң жаққа 3 оңға) оң жаққа 2 = солға (2 ^ {3} оңға) ^ {2} = 64}$

Төртінші ереже - ядро: 4 немесе одан да көп элементтерден тұратын тізбек, 2 немесе одан жоғарыға дейін созылады, (алдыңғы қатарлы элементтермен) бірдей ұзындықтағы тізбекке айналады. Бірақ оның түпкілікті элемент төмендейді, нәтижесінде екінші ереже тізбекті қысқартады. Кейін, сөзді түрлендіру үшін Кнут, «көп бөлшектер», тізбек үш элементке дейін азаяды және үшінші ереже рекурсияны тоқтатады.

Мысалдар

Мысалдар тез күрделене түседі. Міне бірнеше шағын мысалдар:

${ displaystyle n}$

${ displaystyle = n}$ (1 ереже бойынша)

${ displaystyle p to q}$

${ displaystyle = p ^ {q}}$ (5 ереже бойынша)

Осылайша, ${ displaystyle 3 to 4 = 3 ^ {4} = 81}$

${ displaystyle 4 to 3 to 2} дейін$

${ displaystyle = 4 uparrow uparrow 3}$ (3 ереже бойынша)

${ displaystyle = 4 uparrow (4 uparrow 4)}$

${ displaystyle = 4 uparrow 256}$

${ displaystyle = 4 ^ {256}}$

${ displaystyle = 13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,}$ ${ displaystyle 546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096}$

${ displaystyle шамамен 1.34 * 10 ^ {154}}$

${ displaystyle 2 to 2 to a} дейін$

${ displaystyle = 2 [ uparrow ^ {a}] 2}$ (3 ереже бойынша)

${ displaystyle = 4}$ (қараңыз Кнуттың жоғары көрсеткі )

${ displaystyle 2 to 4 to 3} дейін$

${ displaystyle = 2 uparrow uparrow uparrow 4}$ (3 ереже бойынша)

${ displaystyle = 2 жоғары көтеру көтеру (2 көтеру көтеру (2 көтеру көтеру 2))}$

${ displaystyle = 2 uparrow uparrow (2 uparrow uparrow 4)}$

${ displaystyle = 2 жоғары көтеру жоғары көтеру (2 көтеру (2 көтеру (2 көтеру 2)))}$

${ displaystyle = 2 жоғары көтеру көтеру (2 көтеру (2 көтеру 4))}$

${ displaystyle = 2 uparrow uparrow (2 uparrow 16)}$

${ displaystyle = 2 uparrow uparrow (65536)}$

${ displaystyle = {^ {65536} 2}}$ (қараңыз тетрация )

${ displaystyle 2 - 3 - 2 - 2}$

${ displaystyle = 2 -ден 3 -ге (2 -ден 3) -ге дейін 1}$ (4 ереже бойынша)

${ displaystyle = 2 - 3 - 8 - 1} аралығында$ (5 ереже бойынша)

${ displaystyle = 2 to 3 to 8} дейін$ (2 ереже бойынша)

${ displaystyle = 2 жоғары көтеру жоғары көтеру көтеру көтеру көтеру көтеру көтеру көтеру 3 көтеру$ (3 ереже бойынша)

= алдыңғы саннан әлдеқайда көп

${ displaystyle 3 to 2 to 2 to 2}$

${ displaystyle = 3 -ден 2 -ге (3 -ден 2) -ге 1}$ (4 ереже бойынша)

${ displaystyle = 3 - 2 - 9 - 1}$ (5 ереже бойынша)

${ displaystyle = 3 to 2 to 9} дейін$ (2 ереже бойынша)

${ displaystyle = 3 жоғары көтеру көтеру көтеру өсіру көтеру көтеру көтеру көтеру көтеру 2$ (3 ереже бойынша)

= алдыңғы саннан әлдеқайда көп

Жүйелік мысалдар

Төрт мүшеден тұратын қарапайым жағдай (бүтін сандар 2-ден кем болмауы керек):

• ${ displaystyle a to b to 2 to 2}$
  ${ displaystyle = a to b to 2 to (1 + 1)} дейін$
  ${ displaystyle = a to b to (a to b) to 1} дейін$
  ${ displaystyle = a to b to ^ {b}}$
  ${ displaystyle = a [a ^ {b} +2] b}$

(соңғы аталған мүлікке балама)

• ${ displaystyle a to b to 3 to 2}$
  ${ displaystyle = a to b to 3 to (1 + 1)}$
  ${ displaystyle = a to b to (a to b to (a to b) to 1) to 1} дейін$
  ${ displaystyle = a to b to (a to b to a ^ {b})}$
  ${ displaystyle = a [a to b to 2 to 2 + 2] b}$
• ${ displaystyle a to b to 4 to 2} дейін$
  ${ displaystyle = a to b to (a to b to (a to b to a ^ {b}))}$
  ${ displaystyle = a [a to b to 3 to 2 + 2] b}$

Біз мұнда заңдылықты көре аламыз. Егер кез-келген тізбек үшін болса ${ displaystyle X}$, біз рұқсат етеміз ${ displaystyle f (p) = X to p}$ содан кейін ${ displaystyle X to p to 2 = f ^ {p} (1)}$ (қараңыз функционалдық күштер ).

Мұны қолдану ${ displaystyle X = a to b}$, содан кейін ${ displaystyle f (p) = a [p + 2] b}$ және ${ displaystyle a to b to p to 2 = a [a to b to (p-1) to 2 + 2] b = f ^ {p} (1)}$

Мәселен, мысалы, ${ displaystyle 10 to 6 to 3 to 2 = 10 [10 [1000002] 6 + 2] 6}$.

Жылжу:

• ${ displaystyle a to b to 2 to 3}$
  ${ displaystyle = a to b to 2 to (2 + 1)}$
  ${ displaystyle = a to b to (a to b) to 2}$
  ${ displaystyle = a to b to ^ {b} to 2}$
  ${ displaystyle = f ^ {a ^ {b}} (1)}$

Тағы да біз жалпылай аламыз. Біз жазған кезде ${ displaystyle g_ {q} (p) = X to p to q}$ Бізде бар ${ displaystyle X to p to q + 1 = g_ {q} ^ {p} (1)}$, Бұл, ${ displaystyle g_ {q + 1} (p) = g_ {q} ^ {p} (1)}$. Жоғарыдағы жағдайда, ${ displaystyle g_ {2} (p) = a to b to p to 2 = f ^ {p} (1)}$ және ${ displaystyle g_ {3} (p) = g_ {2} ^ {p} (1)}$, сондықтан ${ displaystyle a to b to 2 to 3 = g_ {3} (2) = g_ {2} ^ {2} (1) = g_ {2} (g_ {2} (1)) = f ^ {f (1)} (1) = f ^ {a ^ {b}} (1)}$

Ackermann функциясы

The Ackermann функциясы Conway тізбектелген көрсеткі белгілері арқылы көрсетілуі мүмкін:

${ displaystyle A (m, n) = 2 to (m-2) to (n + 3) -3}$ үшін ${ displaystyle m> 2}$ (Бастап ${ displaystyle A (m, n) = 2 [m] (n + 3) -3}$ жылы гипероперация )

демек

${ displaystyle 2 to m to n = A (m + 2, n-3) +3}$ үшін ${ displaystyle n> 2}$

(${ displaystyle n = 1}$ және ${ displaystyle n = 2}$ сәйкес келеді ${ displaystyle A (m, -2) = - 1}$ және ${ displaystyle A (m, -1) = 1}$, логикалық түрде қосуға болатын).

Грэм нөмірі

Грэм нөмірі ${ displaystyle G}$ оны конвейлік тізбектелген көрсеткіде қысқа түрде білдіруге болмайды, бірақ ол мыналармен шектелген:

${ displaystyle 3 rightarrow 3 rightarrow 64 rightarrow 2$

Дәлел: Біз алдымен аралық функцияны анықтаймыз ${ displaystyle f (n) = 3 rightarrow 3 rightarrow n = { begin {matrix} 3 underbrace { uparrow uparrow cdots uparrow} 3 { text {n strows}} end {matrix }}}$, оның көмегімен Грэмнің нөмірін анықтауға болады ${ displaystyle G = f ^ {64} (4)}$. (64-жоғарғы әріп а-ны білдіреді функционалды қуат.)

2-ереже мен 4-ережені кері қолдану арқылы біз жеңілдетеміз:

${ displaystyle f ^ {64} (1)}$

${ displaystyle = 3 оң жаққа 3 оң жаққа (3 оңға, 3 оңға, ( cdots (3 оңға, 3 оңға, 3 (оңға, 3, оңға, 3ке,),),),)$ (64-мен ${ displaystyle 3 rightarrow 3}$)

${ displaystyle = 3 оң жаққа 3 оң жаққа (3 оң жаққа, 3, оң жаққа ( cdots (3 оңға, 3, оңға, 3 (оңға, 3),), оңға қарай 1) оңға, 1)$

${ displaystyle = 3 rightarrow 3 rightarrow 64 rightarrow 2;}$

${ displaystyle f ^ {64} (4) = G;}$

${ displaystyle = 3 оң жаққа 3 оң жаққа (3 оңға, 3 оңға, ( cdots (3 оңға, 3 оңға, 3 (оңға, солға, 3), оңға, 4)) cdots))}$ (64-мен ${ displaystyle 3 rightarrow 3}$)

${ displaystyle f ^ {64} (27)}$

${ displaystyle = 3 оң жаққа 3 оң жаққа (3 оң жаққа, 3 оңға, ( cdots (3 оңға, 3 оңға, (3 оңға, 3, оңға, 27де))))$ (64-мен ${ displaystyle 3 rightarrow 3}$)

${ displaystyle = 3 оң жақ 3, оң жақ 3 (оң жақ 3, 3-оң жақ (3), 3-оң жақ (3), 3-оң жақ (3), 3-оң жақ (3), 3)$ (65-мен ${ displaystyle 3 rightarrow 3}$)

${ displaystyle = 3 rightarrow 3 rightarrow 65 rightarrow 2}$ (жоғарыдағыдай есептеу).

${ displaystyle = f ^ {65} (1)}$

Бастап f болып табылады қатаң түрде өсуде,

${ displaystyle f ^ {64} (1)$

берілген теңсіздік.

Тізбектелген көрсеткілермен қарағанда әлдеқайда көп санды көрсету өте оңай ${ displaystyle G}$, Мысалға, ${ displaystyle 3 rightarrow 3 rightarrow 3 rightarrow 3}$.

${ displaystyle 3 rightarrow 3 rightarrow 3 rightarrow 3}$

${ displaystyle = 3 оң жақ 3, оң жақ (3 оң жақ 3, оң жақ 27 оң жақ 2) оң жақ, 2 ,}$

${ displaystyle = f ^ {3 оң жақ аралық 3 оң жақ аралық 27 оң жақ аралық 2} (1)}$

${ displaystyle = f ^ {f ^ {27} (1)} (1)}$

бұл Грэм санынан әлдеқайда көп, өйткені бұл сан ${ displaystyle 3 rightarrow 3 rightarrow 27 rightarrow 2}$ ${ displaystyle = f ^ {27} (1)}$ қарағанда әлдеқайда үлкен ${ displaystyle 65}$.

CG функциясы

Конвей мен Гай қарапайым, бір аргументті функцияны құрды, ол бүкіл жазба бойынша диагонализация жасайды, ол келесідей анықталды:

${ displaystyle cg (n) = underbrace {n rightarrow n rightarrow n rightarrow dots rightarrow n rightarrow n rightarrow n} _ {n}}$

мағынасы:

${ displaystyle cg (1) = 1}$

${ displaystyle cg (2) = 2 to 2 = 2 ^ {2} = 4}$

${ displaystyle cg (3) = 3 to 3 to 3 = 3 uparrow uparrow uparrow 3}$

${ displaystyle cg (4) = 4 to 4 to 4 to 4} дейін$

${ displaystyle cg (5) = 5 - 5 - 5 - 5 - 5}$

...

Бұл функция, күтілгендей, өте тез өседі.

Питер Херфордтың кеңейтімі

Питер Хёрфорд, веб-әзірлеуші ​​және статист, осы белгінің кеңейтілуін анықтады:

${ displaystyle a rightarrow _ {b} c = underbrace {a rightarrow _ {b-1} a rightarrow _ {b-1} a rightarrow _ {b-1} dots rightarrow _ {b- 1} a rightarrow _ {b-1} a rightarrow _ {b-1} a} _ {c { text {arrow}}}}}$

${ displaystyle a rightarrow _ {1} b = a rightarrow b}$

Барлық қалыпты ережелер өзгеріссіз қалады.

${ displaystyle a rightarrow _ {2} (a-1)}$ қазірдің өзінде жоғарыда аталғанға тең ${ displaystyle cg (a)}$және функциясы ${ displaystyle f (n) = n rightarrow _ {n} n}$ Конвей мен Гайға қарағанда әлдеқайда жылдам өседі ${ displaystyle cg (n)}$.

Сияқты өрнектерге назар аударыңыз ${ displaystyle a rightarrow _ {b} c rightarrow _ {d} e}$ егер заңсыз болса ${ displaystyle b}$ және ${ displaystyle d}$ әртүрлі сандар; бір тізбекте тек оң жақ көрсеткі болуы керек.

Алайда, егер біз мұны сәл өзгертсек:

${ displaystyle a rightarrow _ {b} c rightarrow _ {d} e = a rightarrow _ {b} underbrace {c rightarrow _ {d-1} c rightarrow _ {d-1} c rightarrow _ {d-1} dots rightarrow _ {d-1} c rightarrow _ {d-1} c rightarrow _ {d-1} c} _ {e { text {arrow}}}}}$

сонда ғана емес ${ displaystyle a rightarrow _ {b} c rightarrow _ {d} e}$ заңды болып шығады, бірақ жазба тұтастай алғанда едәуір күшейеді.^[2]

Сондай-ақ қараңыз

• Штайнгауз-Мозер жазбасы
• Жүйелі түрде жылдам өсетін дәйектіліктер құру

Әдебиеттер тізімі

Сыртқы сілтемелер

• Фактоидтер> үлкен сандар
• Роберт Мунафоның үлкен сандары
• Дж.Х.Конвей мен Р.К.Гайдың сандар кітабы