Божественные натуральные числа

[filin]

Преамбула. Среди математиков гуляет крылатая фраза "Бог создал натуральные числа, остальное - дело рук человека". На самом деле, если википедия и словарь немецкого нам не врут, то Кронекер сказал про целые, а не натуральные, и рук там тоже не было (что логично, остальную математику человек создал по большей части не руками).

Амбула. Предположим, что Бог действительно создал натуральные или целые числа. Из соображений божественности :) понятно, что все-таки натуральные, а не целые, отрицательное число отчетливо небожественно. Таки у меня к вам два вопроса.

1. Какую именно структуру создал Бог?

2. Ноль входит?

Понятно, что натуральные числа можно задавать разными способами. Понятно, что просто натуральный ряд, без операций, Бог не создавал, смысла нет. Понятно, что, скажем, вычитание и деление не входят (множество натуральных чисел относительно них не замкнуто). Очевидно, что и, скажем, факториал тоже придуман людьми. А какие операции божественны?

Я ставлю на: единицу (ноль не входит), следующее число (AKA +1), и... а вот что "и"? В основаниях математики тут используют рекурсию. Но рекурсия - понятие, мягко говоря, недетской сложности, его в школе до сих пор фактически не дают. Даже в вузах проходят построение целых чисел, рациональных, предела, действительных, производной, интеграла, и с легкостью доходят до гребеней математической статистики, рекурсию даже не упомянув. Между тем сложение детям, если объясняют, то объясняют по сути через примитивную рекурсию... Хотя нет, через итерацию. Через разворачивание числа в последовательность. Умножение тоже так вводят. "... и понятие последовательности"?

Comments

[filin]

Боюсь, что попытка совместить общий случай (т.е. никаких дополнительных условий) c завершением в один шаг приводит к общерекурсивному мю-оператору, т.е. к неразрешимой проблеме. А это неконструктивно.

А в примитивно-рекурсивном случае завершение происходит именно в частном случае (а нифига не вырожденном, кстати - антитезой общему случаю будет частный) и не может происходить иначе.

[slobin]

По-моему, проблема останова в рекурсивном случае не страшнее, чем в итеративном. Если вас смущает рекурсия, но не смущает ряд Коллатца (n := odd(n) ? 3n+1 : n/2)... ну я не знаю. А проблема, на мой взгляд, именно в том, что частный случай в программах, написанных понимающими рекурсию людьми, почему-то оказывается заодно и вырожденным. Ну, например... нет, не факториал. :-) Давайте определим ну хотя бы понятие "сумма n чисел". Для нормального человека простейший ("содержательный") частный случай -- это когда n=2. И сведение n=3 к n=2, n=4 к n=3 и так далее трудностей, по-моему, не вызывает. Но уже даже случай n=1 слегка нервирует, а уж n=0...

"Сумма ничего есть ничего" -- это игра слов, потому что произведение ничего равно единице, а чему равна конъюнкция ничего -- мне приходится каждый раз заново решать эту задачу в обратную сторону: чему она должна быть равна, чтобы применять рекурсию? Мне кажется, что если бы реальный код останавливался на n=2, то он был бы гораздо понятнее. Правда, у этого есть другая сторона: не факт, что он правильно работал бы при n=1 и n=0. А если и работал бы, то случайно. Я не знаю, что с этим делать.

P.S. В языке k (это такой потомок APL) пустых списков пять -- гетерогенный и четыре гомогенных по четырём базовым типам. Забавно, как они печатаются, какой вид автор считает "каноническим изображением": (), !0, 0#0.0, "" и 0#`

... Я купил за три рубля компилятор с паскаля ...

[filin]

Сумма ничего и произведение ничего используют единицу полугруппы, если она есть. Ну, левую или правую, если они различны, в зависимости от того, foldl там или foldr. Это как раз понятно. Но при этом в хаскеле им эту единицу надо указать явно (что заодно позволяет использовать у элемента списка и результата разные типы, и это порой вельми удобно). Но fold - он по жизни гораздо толще, чем просто суммирование последовательности.

Есть еще foldr1 и foldl1, которым единицу указывать не надо, но которые за это на пустом списке хряпаются. Как раз тот случай с естественной размерностью - посчитать яблоки можно только если есть хотя бы одно. На одноэлементном списке работают правильно. Вот они как раз соответствуют идее "сложить последовательность". Что тут важно. Одноэлементная последовательность считается валидной последовательностью в смысле данной задачи. Для нее понятие суммы поэтому приходится доопределять. После чего n=2 уже превращается из частного случая в общий. Хотя (снова в тему "первый-второй") одноэлементная последовательность - это таки да, вырожденная последовательность. (А пустая - совершенно вырожденная.) А так-то, естественным образом, говоря о сумме или произведении последовательности, нужно иметь хотя бы два элемента - операция-то бинарная.

Другое дело, что на самом деле задач суммирования последовательностей не бывает. На самом деле бывает только задача интегрирования, а это fold в чистом виде с явным заданием стартового значения, и да, с типом результата, на самом деле отличным от типа элемента последовательности, даже если случайно совпавшим (так, размерность факториала - количество перестановок, а его аргумента - количество элементов, яблоки и крокодилы). И именно по этой причине про foldr/foldl помнят все, а про foldr1/foldl1 напрочь забывают. Применений у них практически нет, а те, что есть - извращенные.