![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
о функциях
Alien Coding: https://arxiv.org/abs/2301.11479
Интересная статья. Авторы придумали специальный очень упрощенный язык программирования, так, что особенно удобно генерировать программы на нем (любой случайный набор токенов что-то вычисляет). Потом они взяли все 360 тысяч последовательностей натуральных чисел проекта OEIS, и с помощью нейронных сетей искали простые программы, вычисляющие разные последовательности. Им удалось найти 80 тысяч совпадений.
Они назвали это "alien coding", видимо, потому, что идея в том, чтобы найти программу для вычисления последовательности, не основываясь на нашем, "человеческом", понимании ее смысла. Ну вот возьмем, например, последовательность A027193. Она выглядит так: 0, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 29, 37, 52, 66... где на n-том месте стоит число разложений n на нечетное число слагаемых. Например 6 можно представить как [6], [4+1+1], [3+2+1], [2+2+2], [2+1+1+1+1] - всего пять способов так, чтобы число слагаемых было нечетным, и поэтому на 6-м месте в последовательности стоит 5 (места считают с нуля). Зная это правило, мы можем написать программу, которая вычисляет эту последовательность. Но может оказаться, что если науськать на нее нейронную сеть, она найдет какую-то совершенно другую программу, которая бац-бац-бац делает какие-то вычисления с n, сути которых мы не понимаем, и получаются все правильные числа: 0, 1, 1, 2, 2, 4, 5, ... итд. Если постараться вникнуть в смысл кода, который нашла нейронная сеть, то может оказаться, что он по сути находит именно это число разбиений; а может, пользуется каким-то другим математическим свойством этой последовательности, которое нам еще неизвестно.
Интересное дело, короче. Я посмотрел на несколько таких программ в их репозитории https://github.com/Anon52MI4/oeis-alien (почему-то ведется анонимно, не могу понять смысла этого; на репозиторий есть ссылка в статье). Там кроме программы на их "странном" языке дается автоматический перевод в Питон. Заодно стали понятны и некоторые ограничения этого исследования. Они основываются только на первых 32 числах каждой последовательности. Это значит, я думаю, что будет много ложных совпадений, т.е. программ, которые совпадают с данной последовательностью OEIS на первых 32 числах, но в какой-то момент начинают расходиться.
Довольно быстро нашел пример такого ложного совпадения: последовательность https://oeis.org/A277094, "Числа k, такие, что sin(k)>0 и sin(k+2)<0". Она начинается так: 2 3 8 9 14 15 20 21 27 28 33 34 39... Мы видим, что идут по два числа подряд, потом пропуск, опять два числа подряд итд. Пропуск обычно размером в 5 (как между 3 и 8), но иногда в 6 (как между 21 и 27). Если посмотреть дальше, то видна закономерность: четыре пропуска в 5, один в 6, три в 5, один в 6, потом опять повторяется: четыре в 5, один в 6, три в 5, один в 6, итд. Программа, которую нашла нейронная сеть, нашла способ вычислить эту последовательность с помощью нескольких простых вычислений (вы можете посмотреть на код, https://github.com/Anon52MI4/oeis-alien#numbers-k-such-that-sink--0-and-sink2--0, упростить его и разобраться). И это отлично работает! Проблема в том, что то, что я только что описал - это лишь приближение к настоящей A277094, с ее смыслом про синусы. Оно возникает от того, как числа, кратные числу пи/2, "укладываются" между натуральными числами. Из-за иррациональности пи/2 есть все основания ожидать, что такое строгое правило "четыре раза пропуск 5, один раз 6, три раза 5, один раз 6", не может повторяться бесконечно; будет накопление маленькой ошибки, которое в конце концов перейдет в другой сдвиг очередного члена. И действительно, это происходит на члене номер 113 (а программа смотрела только на первые 32). Не знаю, какая тут мораль, но вот так получилось. Интересная штука.
Интересная статья. Авторы придумали специальный очень упрощенный язык программирования, так, что особенно удобно генерировать программы на нем (любой случайный набор токенов что-то вычисляет). Потом они взяли все 360 тысяч последовательностей натуральных чисел проекта OEIS, и с помощью нейронных сетей искали простые программы, вычисляющие разные последовательности. Им удалось найти 80 тысяч совпадений.
Они назвали это "alien coding", видимо, потому, что идея в том, чтобы найти программу для вычисления последовательности, не основываясь на нашем, "человеческом", понимании ее смысла. Ну вот возьмем, например, последовательность A027193. Она выглядит так: 0, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 29, 37, 52, 66... где на n-том месте стоит число разложений n на нечетное число слагаемых. Например 6 можно представить как [6], [4+1+1], [3+2+1], [2+2+2], [2+1+1+1+1] - всего пять способов так, чтобы число слагаемых было нечетным, и поэтому на 6-м месте в последовательности стоит 5 (места считают с нуля). Зная это правило, мы можем написать программу, которая вычисляет эту последовательность. Но может оказаться, что если науськать на нее нейронную сеть, она найдет какую-то совершенно другую программу, которая бац-бац-бац делает какие-то вычисления с n, сути которых мы не понимаем, и получаются все правильные числа: 0, 1, 1, 2, 2, 4, 5, ... итд. Если постараться вникнуть в смысл кода, который нашла нейронная сеть, то может оказаться, что он по сути находит именно это число разбиений; а может, пользуется каким-то другим математическим свойством этой последовательности, которое нам еще неизвестно.
Интересное дело, короче. Я посмотрел на несколько таких программ в их репозитории https://github.com/Anon52MI4/oeis-alien (почему-то ведется анонимно, не могу понять смысла этого; на репозиторий есть ссылка в статье). Там кроме программы на их "странном" языке дается автоматический перевод в Питон. Заодно стали понятны и некоторые ограничения этого исследования. Они основываются только на первых 32 числах каждой последовательности. Это значит, я думаю, что будет много ложных совпадений, т.е. программ, которые совпадают с данной последовательностью OEIS на первых 32 числах, но в какой-то момент начинают расходиться.
Довольно быстро нашел пример такого ложного совпадения: последовательность https://oeis.org/A277094, "Числа k, такие, что sin(k)>0 и sin(k+2)<0". Она начинается так: 2 3 8 9 14 15 20 21 27 28 33 34 39... Мы видим, что идут по два числа подряд, потом пропуск, опять два числа подряд итд. Пропуск обычно размером в 5 (как между 3 и 8), но иногда в 6 (как между 21 и 27). Если посмотреть дальше, то видна закономерность: четыре пропуска в 5, один в 6, три в 5, один в 6, потом опять повторяется: четыре в 5, один в 6, три в 5, один в 6, итд. Программа, которую нашла нейронная сеть, нашла способ вычислить эту последовательность с помощью нескольких простых вычислений (вы можете посмотреть на код, https://github.com/Anon52MI4/oeis-alien#numbers-k-such-that-sink--0-and-sink2--0, упростить его и разобраться). И это отлично работает! Проблема в том, что то, что я только что описал - это лишь приближение к настоящей A277094, с ее смыслом про синусы. Оно возникает от того, как числа, кратные числу пи/2, "укладываются" между натуральными числами. Из-за иррациональности пи/2 есть все основания ожидать, что такое строгое правило "четыре раза пропуск 5, один раз 6, три раза 5, один раз 6", не может повторяться бесконечно; будет накопление маленькой ошибки, которое в конце концов перейдет в другой сдвиг очередного члена. И действительно, это происходит на члене номер 113 (а программа смотрела только на первые 32). Не знаю, какая тут мораль, но вот так получилось. Интересная штука.
no subject
Программы для последовательностей на языке Java. Всё честно, пишется людьми (или программами, написанными людьми). Покрыли уже сумасшедшие 150 тысяч последовательностей, почти 3/7 от общего объёма Энциклопедии.
2) Sequence Machine: http://sequencedb.net
По данной последовательности подбирает, как она связана с другими. Тоже по нескольким первым членам. Масса ложных формул, немало тривиальных истинных, но находил я и довольно много не таких уж тривиальных истинных, и даже одну весьма правдоподобную формулу для последовательности без полноценного описания.