(Оффтоп)
arseniiv
Ну, всё-таки сложность объективно существует. Что, впрочем, не означает, что существует "слишком сложность".
Я пока не могу сказать, что верю, что сложность существует объективно. Хотя сложность для человеческой головы — да.
![Very Happy :D](./images/smilies/icon_biggrin.gif)
Ну, речь, видимо, про неё.
Да я не у него интересуюсь.
В «Конкретной математике» было специальное отступление о том, что там будет пониматься под замкнутой формой, потому что просьба найти замкнутую форму там встречается в задачах. Сейчас поищу его.
Сначала замкнутая форма встречается по отношению к решению рекуррентных соотношений, и никак не определяется, хотя можно посчитать, что это форма вида
![$a_n = \langle\text{здесь не встречаются термы вида}\,a_t\rangle$ $a_n = \langle\text{здесь не встречаются термы вида}\,a_t\rangle$](https://dxdy-04.korotkov.co.uk/f/b/7/7/b77cb5450a905f64ec83756afc8a386f82.png)
. Несколько позже встречаем
Страница с верхним колонтитулом «24 Возвратные задачи // 1.2 Задача о разрезании пиццы» писал(а):
Между прочим, мы разглагольствуем о „замкнутых формах“ без точного определения, что мы под этим понимаем. Обычно это и так достаточно очевидно. Рекуррентности типа (1.1) и (1.4) представлены в незамкнутой форме, ибо они выражают некоторую величину через самое себя, но их решения типа (1.2) и (1.6) — в замкнутой форме. Суммы вида
![$1+2+\ldots+n$ $1+2+\ldots+n$](https://dxdy-02.korotkov.co.uk/f/5/7/f/57fd7a316e7c4e5eea461a7014ddc67282.png)
записаны не в замкнутой форме, поскольку они грешат наличием
![`$\ldots$' `$\ldots$'](https://dxdy-02.korotkov.co.uk/f/5/e/8/5e81d85b1ef1ede81df0c224d27ea49882.png)
; но выражения вида
![$n(n+1)/2$ $n(n+1)/2$](https://dxdy-01.korotkov.co.uk/f/8/9/4/89482dff9ccffa2a049b0e5e090ba4d682.png)
представлены в замкнутой форме. Можно дать некое грубое определение типа следующего: выражение для величины
![$f(n)$ $f(n)$](https://dxdy-04.korotkov.co.uk/f/3/d/4/3d425a215e8eeb2a056f553633aaae4a82.png)
представлено в замкнутой форме, если ее можно вычислить с помощью некоторого фиксированного числа „известных“ стандартных операций, независимо от
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
. Например, выражения
![$2^n-1$ $2^n-1$](https://dxdy-04.korotkov.co.uk/f/f/e/9/fe9381b12bf563bf6fe9b69a65836f3082.png)
и
![$n(n+1)/2$ $n(n+1)/2$](https://dxdy-01.korotkov.co.uk/f/8/9/4/89482dff9ccffa2a049b0e5e090ba4d682.png)
представлены в замкнутой форме, поскольку они включают в себя только
сложение, умножение, деление и возведение в степень в явном виде.
Общее число простых замкнутых форм ограничено, так что существуют рекуррентности, которые не представимы в простых замкнутых формах. Но если такие рекуррентности возникают постоянно, демонстрируя свою важность, — мы пополняем свой репертуар новыми операциями; это может существенно расширить диапазон задач, решаемых в „простой“ замкнутой форме. К примеру, произведение первых
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
целых чисел,
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
факториал, оказалось настолько важным, что теперь все мы рассматриваем его как основную операцию. Поэтому формула
![`$n!$' `$n!$'](https://dxdy-03.korotkov.co.uk/f/2/f/e/2feb4b05e4083a142224dc1ed63828c582.png)
записана в замкнутой форме, хотя эквивалентное ей выражение
![`$1\cdot2\cdot\ldots\cdot n$' `$1\cdot2\cdot\ldots\cdot n$'](https://dxdy-04.korotkov.co.uk/f/b/f/a/bfad346c33d84f89bef73c2f7d7a351a82.png)
— нет.
-- Ср июн 25, 2014 20:36:43 --Я таких слов даже не знаю, Вы ошиблись...
Действительно. Автор цитаты-то не тот.
-- Ср июн 25, 2014 20:45:36 --Короче говоря, «терм
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
— в замкнутой форме» обозначает какое-то из «
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
— в
![$\Sigma$ $\Sigma$](https://dxdy-01.korotkov.co.uk/f/8/1/3/813cd865c037c89fcdc609b25c465a0582.png)
-замкнутой форме» с набором функциональных символов
![$\Sigma$ $\Sigma$](https://dxdy-01.korotkov.co.uk/f/8/1/3/813cd865c037c89fcdc609b25c465a0582.png)
, берущимся из контекста, и которое понимается как
![$\exists f\in\Sigma : t = f(t_1,\ldots t_n)$ $\exists f\in\Sigma : t = f(t_1,\ldots t_n)$](https://dxdy-01.korotkov.co.uk/f/4/0/b/40bee3881106c1c5eeb8c99714f7458982.png)
и все
![$t_i$ $t_i$](https://dxdy-01.korotkov.co.uk/f/0/2/a/02ab12d0013b89c8edc7f0f2662fa7a982.png)
находятся в
![$\Sigma$ $\Sigma$](https://dxdy-01.korotkov.co.uk/f/8/1/3/813cd865c037c89fcdc609b25c465a0582.png)
-замкнутой форме.
-- Ср июн 25, 2014 20:53:33 --Например, в случае выразимости в радикалах для корней многочленов
![$\Sigma$ $\Sigma$](https://dxdy-01.korotkov.co.uk/f/8/1/3/813cd865c037c89fcdc609b25c465a0582.png)
равна чему-то вида
![$\{1,+,-,\cdot,/,a_1,\ldots,a_n,\sqrt{\hphantom{a}}\}$ $\{1,+,-,\cdot,/,a_1,\ldots,a_n,\sqrt{\hphantom{a}}\}$](https://dxdy-01.korotkov.co.uk/f/0/c/2/0c213744d18520976ac129d1016eafc582.png)
. Ну, это все знают, я просто выписал для предлагаемого определения, да и один и тот же класс замкнутых форм может рождаться разными
![$\Sigma$ $\Sigma$](https://dxdy-01.korotkov.co.uk/f/8/1/3/813cd865c037c89fcdc609b25c465a0582.png)
(всё, разумеется, в фиксированном языке).