Русская Википедия:Гипероператор
Гиперопера́тор — обобщение традиционных арифметических операций — сложения, умножения и возведения в степень, рассматриваемых как гипероператоры 1-го, 2-го и 3-го порядка соответственно, — на высшие порядки (тетрация, пентация и так далее).
В силу некоммутативности (в общем случае) гипероператор имеет две обратные функции — гиперкорень и гиперлогарифм. Гиперкорень и гиперлогарифм сложения и умножения совпадают, образуя вычитание и деление соответственно, но уже для возведения в степень обратные функции становятся различными (корень и логарифм). Обратные операции обобщаются для гипероператора любого порядка.
История
Исторически первым гипероператором является функция Аккермана (1928), сконструированная как пример всюду определённой не являющейся примитивно рекурсивной вычислимой функции от трёх аргументов <math> \varphi(a,b,n)</math> такой, что для <math>n=0,1,2</math> она определяла операции сложения, умножения и возведения в степень соответственно:
- <math> \varphi(a,b,0)=a+b</math>,
- <math> \varphi(a,b,1)=a\cdot b</math>,
- <math> \varphi(a,b,2)=a^b</math>;
в стрелочной нотации Кнута[1]:
- <math> \varphi(a,b,n)=a\uparrow^{n-1}(b+1)</math>.
Впоследствии Гудстейном были разработаны последовательности функций, более аккуратно реализующие концепцию гипероператоров.
Определение
Гипероператор порядка <math>n</math> с аргументами <math>a</math> и <math>b</math> (далее обозначаемый как <math>a^{(n)}b</math>) рекурсивно определяется как результат многократного применения гипероператора порядка <math>n-1</math> к последовательности из <math>b</math> одинаковых аргументов, (начиная с умножения, каждый из которых равен <math>a</math>):
- сложение <math>a</math> и <math>b</math> — увеличение числа <math>a</math> на количество единиц, равное <math>b</math>: <math> a {^{(1)}} b = a + \underbrace{1 + 1 + \dots + 1}_{b} = a + b</math>
- умножение <math>a</math> на <math>b</math> — сложение числа <math>a</math> с самим собой <math>b</math> раз: <math> a {^{(2)}} b = \underbrace{a + a + \dots + a}_{b} = a \times b </math>
- возведение a в степень b — умножение числа <math>a</math> на само себя <math>b</math> раз: <math> a {^{(3)}} b = \underbrace{a \times a \times \dots \times a}_{b} = a^b </math>
- <math>...</math>
- <math> a {^{(n)}} b = \underbrace{a^{(n-1)} a^{(n-1)} \dots a^{(n-1)} a}_{b} </math>
В последнем выражении операции выполняются справа налево, что является существенным, так как гипероператоры порядка <math>n>2</math> не являются ни коммутативными, ни ассоциативными. Гипероператоры 4-го, 5-го и 6-го порядка называются «тетра́ция», «пента́ция» и «гекса́ция» соответственно.
В простейшем случае значения переменных <math>a</math>, <math>b</math> и <math>n</math> ограничиваются натуральными числами. Возможные обобщения гипероператоров <math>n\geqslant4</math> на произвольные действительные или комплексные числа пока мало изучены.
Разные математики обозначают гипероператоры по-разному; Кнут использует стрелки <math>\uparrow</math>, Конвей использует стрелки <math>\to</math>:
- <math>a {^{(n)}} b = \textrm{hyper}(a,n,b) = a \uparrow^{n-2} b = a \to b \to (n-2)</math>.
Альтернативные операции
Альтернативная операция может быть получена путём вычисления слева направо и в силу коммутативности и ассоциативности операций сложения и умножения эта операция совпадает с гипероператором при <math>n<4</math>:
- <math>a+b = (a+(b-1))+1</math>,
- <math>a\times b = (a\times (b-1))+a</math>,
- <math>a^b = (a^{(b-1)})\times a</math>.
Для гипероператора <math>n\geqslant4</math> вычисление слева направо (то есть альтернативная операция) отличается от гипероператора и проводит к другому результату, например, для <math>n=4, a=3, b=3</math> получим гипероператор тетрацию: <math> 3\uparrow^{2}3={}^33=3^{3^3}=3^{27}=7\text{ }625\text{ }597\text{ }484\text{ }987</math>.
Но вычисление степенной башни слева направо приведёт к неверному итогу: <math>3^{3^3}\neq \left(3^3\right)^3=3^{3^2}=3^{9}=19\text{ }683</math>.
Примечания
Литература
