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

[filin]

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

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

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

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

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

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

Comments

[elentin]

Раз. Я (как пидагох) разделяю такую нетривиальную точку зрения что чем раньше детям что-то расскажешь, тем легче им потом будет в старшей школе (ну, с определённого возраста, после 7 лет, мы же школьников обсуждаем, абстрактное мышлениедолжно появиться, младенчиков можно обсудить отдельно, тут я как раз против "раннего развития"). Ну, т.е. 1-2-классникам вполне можно рассказывать циклы, скажем, про это есть пара удачных учебников и среда программирования Пиктомир. Почему бы и не рекурсию шестиклассникам рассказать? (Могу спросить у коллег, которые более регулярно, чем я в последнее время, рассказывают что-то шестиклассникам - а и спрошу, пожалуй).

Два. Всякий, кого как-то учили формальной логике, по-моему, знает, что можно вот из чего числа соорудить: "сделать множество из того, что внутри" и "пустое множество". {}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}} etc. - есть ли тут рекурсия?

И, да, про Кронекера мне как-то всегда казалось, что бог - натуральнве, а человек - всё остальное без уточнений, руками или чем-то ещё, ноя не заглядывала в оригинал.

[filin]

Ты вот Сэнту знаешь? Вот она жаловалась, что не понимает рекурсию. И натурально, не она одна. Нет, идею "позвать ту же функцию с другими параметрами" можно школьнику рассказать, и он ее прекрасно схватит. А вот идею, что первое, о чем надо думать - это о гарантии завершения, - уже нет. Я уж не говорю о разнице между примитивной и общей рекурсиями и отдельно - об особенности хвостовой рекурсии. В математике, правда, хвостовость традиционно несущественна, но даже в математике уже все-таки начали различать не только разрешимые и неразрешимые задачи, но и практически разрешимые, и считать хотя бы асимптотику глубины стека :)

Короче, рекурсия как математический аппарат требует куда более развитого абстрактного мышления, чем освоение умножения через сложение.

Два. Не всякий. Если формальной логике учили пятиклассника, то со связками и кванторами он обращаться научается довольно неплохо, а вот с идеей так строить числа освоится вряд ли. Ну и эта... Хорошо, построить ты так числа сможешь. А оперировать с ними? Ну-ка, сложи 2 и 2 в таком представлении...

Вот тут как раз Кир приводил другую цитату, про то, что итерация от человека, а рекурсия от бога. В смысле, требуется божественный уровень понимания...

Нутром чую понятие последовательности, но доказать не могу...

[slobin]

Мне в последнее время кажется, что все сложности в понимании рекурсии оттого, что завершение традиционно происходит в тот же самый момент, когда общий случай сводится к вырожденному. А это ("завершение" и "общий vs вырожденный") два разных понятия, которые мы таким образом успешно перемешиваем в головах. Мне кажется, что софизм "все лошади одинакового цвета" как раз на эксплойте этой трудности построен.

... Трудно быть багом ...

[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 напрочь забывают. Применений у них практически нет, а те, что есть - извращенные.

[p_govorun]

Рекурсия действительно не вмещается в человеческий мозг. Я только что сказал «рекурсия не вмещается в человеческий мозг -- и это действительно так». Предыдущее высказывание неверно, хотя и является высказыванием о верном высказывании.

Может ли первоклассник разобраться в предыдущем абзаце? Для этого ведь и взрослому придётся соответствующим образом вывернуть мозг.