Сумма сдвигов псевдослучайной последовательности и предикция

[CSV3]

Дано:
1. Есть порождающая псевдослучайная последовательность (ПСП) P, элементами которой являются натуральные числа в интервале от 0 до некоего небесконечного числа Q, дополнительно ограниченного разрядной сеткой вычислителя (например, целочисленное беззнаковое, 32 бит).
2. Длина периода L ПСП неизвестна, но может на многие порядки превышать объем памяти реального вычислителя (скажем, L много больше 10 в степени 15), аналитическое выражение для генерации ПСП неизвестно.
3. Есть ПСП S, полученная из P следующим образом: S образуется суммированием конечного (но чрезмерно большого с точки зрения технических возможностей вычислителя) количества M сдвинутых копий исходной ПСП P (в начале каждой ПСП Pi дописывается некое количество нулей Ni, причем образованная последовательность SH длин сдвигов N1..NM также является в свою очередь псевдослучайной, с неизвестным аналитическим выражением и неизвестным периодом, но ограниченным сверху длиной периода L.
Задача :
1. Сверхслабая. Можно ли, считая что вычислительная мощность и память гипотетического вычислителя не ограничена, сгенерировать из массива S строку D с длиной L, корреляционная функция которой K (P, D) будет отличаться от нуля и не будет меньше некоего заданного практического значения.
2. Слабая. То же самое, что №1, но при ограниченной вычислительной мощности (например, современных экзафлопных суперкомпьютеров) и при ограничении длины строки D значениями, диктуемыми техническими возможностями практического вычислителя.
3. Умеренная. Можно ли при ограниченной вычислительной мощности восстановить из массива S строку D, которая будет представлять собой субстроку из P, начиная с первого элемента P, длиной не менее заданного практического числа (скажем, 1000000... 1000000000).
4. Сильная. То же , что №3, но с восстановлением из S субстроки последовательности SH с заданной практической длиной этой субстроки.
5. Сверхсильная. Полное восстановление P и SH, при неограниченных вычислительной мощности и количества памяти.

Возможно, я где-то пропустил что-то тривиальное, что сразу даст ответы на все вопросы... поэтому и обратился к форуму )

[mihaild]

Я правильно понимаю, что неизвестность аналитического выражения означает, что решение должно работать для произвольных последовательностей?
Т.е. у нас есть периодические последовательности $P$ и $N$. $S_i = P_{i - N_1} + P_{i - N_2} + \ldots + P_{I - N_M}$ (если бы Вы написали формулы в $\TeX$, читать было бы гораздо приятнее), причем считаем $P_j = 0$ при $j < 0$. И мы хотим по $S$ что-то найти.
Вроде перспектив нет, варианты $P_i = \delta_{ij}$, $N_1 = K - j$ дают одинаковую $S$ для всех $j < K$.

[CSV3]

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

-- 21.03.2026, 23:01 --

Я вообще полагал, что эта задача, представляющая из себя как бы расширение обычного варианта пары сигнал-отражения, но при одном маленьком нюансе, что сигнал отправили не мы сами, уже возникала там и сям. Однако сходу не нашел. Фактически, как я сам только что подумал, эта задача подобна поиску искусственного, структурированного начала в шумах из Вселенной, которые могут претерпевать задержки/переотражения в процессе распространения. Причем с момента появления проекта CETI компьютеры имеют мощности на 12 порядков выше тогдашних...

[CSV3]

Если бы возник вопрос, касающийся аналогии с сигналами Вселенной - а откуда вдруг взялись какие-то задержки/переотражения, то это уже несколько иная тема для физического раздела форума. Эта тема касается некоей физической теории, которую я воздвигаю уже довольно давно. Она дает необычные, идущие вразрез с устоявшимися представлениями выводы. Например, она объясняет наблюдение войдов совсем иными причинами, чем приняты в астрофизике. Со скоростью света эта теория вообще обращается весьма неожиданно. Одним из маленьких следствий, согласно этой теории, и является превращение любого достаточно сложного, структурированного сигнала в псевдошум (с точки зрения отправителя)/шум (с нашей точки зрения), если сигнал прошел достаточно большое расстояние в галактическом пространстве. В этой связи вопрос "где все?" начинает наполняться иным смыслом. Можно представить, что любая развитая цивилизация, которая уже знает про особенности распространения информации во Вселенной, не особо интересуется теми, кто еще не очень развился. И поэтому, вместо отправки тарелкой простой модулированной синусоиды на частоте, кратной числу Пи, помноженному на частоту сверхтонкого перехода атома водорода, такие цивилизации отправляют тщательно синтезированные, сложноструктурированные сигналы дискретной природы, из многих источников. Грубо говоря, нам не хочется тратить время на общение с аборигенами сигнальными флажками, мы сидим в своем сообществе, в инете на оптике. Эти сигналы трансформируются Космосом и воспринимаются слушающей цивилизацией просто как шум, если такая цивилизация еще не достигла уровня развития, позволяющего восстановить исходный сигнал. Соответственно, и прием простенького модулированного сигнала, который, согласно вышеупомянутой теории, не претерпит существенных изменений на своем пути, говорит развитой цивилизации о том, что отправила этот сигнал система, которая еще только на пороге знаний.

Таким образом, задача, упрощенно обрисованная в первом посте (упрощение - переход от вещественного поля к целочисленному в результате квантования и дискретизации при приеме, без знания о параметрах квантования и дискретизации, применяемых при генерации сигналов), и при условии верности теории, оборачивается двумя сторонами, которые при этом идут рядом:

1. Обнаружение некоей информации, структуры в шумах, принятых из Космоса.
2. Улучшение отношения сигнал/шум в системах дальней космической связи (разумеется, не все, что летит из дальнего космоса, считается сообщениями от братьев по разуму, но способность восстанавливать любой исходный сигнал из суммы со сдвигами, либо вычислять сигнал с некими ощутимыми корреляционными свойствами автоматически будет означать предикцию и улучшение отношения сигнал/шум).

[tolstopuz]

Решение этой задачи может помочь еще в одной известной проблеме - коде Торы. Пока анализ Торы ограничивается простейшими эвристиками типа взять каждую 50-ю букву, но этот новый способ может привести к прорыву в понимании кода. Кстати, есть подозрение, что священные тексты нам оставили инопланетяне.

https://www.skeptik.net/religion/judaism/toracode.htm

Лем писал(а):

Программирование магии заняло более двух лет. Трудностей хватало. Пришлось повозиться, например, с переводом заклинаний американских индейцев, записанных узелковым письмом «кипу», и с ледово-снежными заклятиями курильских племен и эскимосов

А. и Б. писал(а):

В институте снова появился Выбегалло. Везде ходит и хвастается, что осенён титанической идеей. Речь многих обезьян, видите ли, напоминает человеческую, записанную, значить, на магнитофонную плёнку и пущенную задом наперёд с большой скоростью. Так он, эта, записал в сухумском заповеднике разговоры павианов и прослушал их, пустив задом наперёд на малой скорости. Получилось, как он заявляет, нечто феноменальное, но что именно — не говорит.

[CSV3]

tolstopuz в сообщении #1720874 писал(а):

Решение этой задачи может помочь еще в одной известной проблеме - коде Торы. Пока анализ Торы ограничивается простейшими эвристиками типа взять каждую 50-ю букву, но этот новый способ может привести к прорыву в понимании кода. Кстати, есть подозрение, что священные тексты нам оставили инопланетяне.

Товарищ... я на различных форумах бывал в общей сложности лет 30. И прекрасно осведомлен о всех, так сказать, индивидах, подтипах и внутримарковских цепях наших форумов, которые преобразуются в истинно случайный шум либо в ПСП "Логодиаррея". Поэтому, если вам нечего сказать, а ваши регалии ограничиваются цифиркой у аватара, то вы можете свободно пройти сквозь ушко альтернативной ветки №7930946780238 (выбирал специально для вас, численными методами, на базе вашего профиля). Я пишу это не в ЛС, дабы профилактировать.

[Someone]

CSV3 в сообщении #1720838 писал(а):

Разумеется, по определению это аналитическое выражение единственно

Так не бывает. Для любой конечной последовательности найдётся бесконечное количество различных аналитических выражений, дающих различные продолжения.

[Ende]

CSV3 в сообщении #1720843 писал(а):

Эта тема касается некоей физической теории, которую я воздвигаю уже довольно давно. Она дает необычные, идущие вразрез с устоявшимися представлениями выводы. Например, она объясняет наблюдение войдов совсем иными причинами, чем приняты в астрофизике. Со скоростью света эта теория вообще обращается весьма неожиданно.

За такие теории на нашем форуме банят. Так что не надо о Вселенной, поставьте корректную математическую задачу и решайте ее.
Задача в стартовом посте поставлена некорректно, на что Вам уже указали выше:

Someone в сообщении #1720880 писал(а):

Для любой конечной последовательности найдётся бесконечное количество различных аналитических выражений, дающих различные продолжения.

[CSV3]

Ende в сообщении #1720882 писал(а):

CSV3 в сообщении #1720843 писал(а):

Эта тема касается некоей физической теории, которую я воздвигаю уже довольно давно. Она дает необычные, идущие вразрез с устоявшимися представлениями выводы. Например, она объясняет наблюдение войдов совсем иными причинами, чем приняты в астрофизике. Со скоростью света эта теория вообще обращается весьма неожиданно.

За такие теории на нашем форуме банят. Так что не надо о Вселенной, поставьте корректную математическую задачу и решайте ее.
Задача в стартовом посте поставлена некорректно, на что Вам уже указали выше:

Someone в сообщении #1720880 писал(а):

Для любой конечной последовательности найдётся бесконечное количество различных аналитических выражений, дающих различные продолжения.

Уточнил исходные, в меру своих познаний. Постулируется, что аналитическое выражение выбрано отправителем, оно единственное, но неизвестно получателю. Ну а теории... я просто привел аналогию, которая быстро раскрывает суть вопроса. Стоит множество маяков, которые всенаправленно генерируют одну и ту же структурированную посылку, и в результате временных сдвигов и весьма высокой изотропности этой сети получатель принимает все это как псевдошум/шум. Что это за маяки, зачем они стоят... это уже можно считать просто отвлеченной аналогией некоей умозрительной математической задачи. Я вообще не исключал, что для математика ответ сразу лежит на поверхности - 1. Нет, не получится, 2. Получится. В инженерной практике или при изысканиях я не сталкивался именно с такой формулировкой задачи. Все было более-менее обычно, сигнал с наперед заданными характеристиками- сдвиги, фазы. Или та же очистка от реверберационных хвостов, где в начале сигнала мы имеем исходный образец.

[zykov]

CSV3 в сообщении #1720888 писал(а):

Стоит множество маяков, которые всенаправленно генерируют одну и ту же структурированную посылку, и в результате временных сдвигов и весьма высокой изотропности этой сети получатель принимает все это как псевдошум/шум

Ну они не просто складываются, а складываются с разными весами, т.к. находятся на разном расстоянии и будут иметь разную интенсивность в принимающей точке.
Кроме того, зачем ограничиваться сигналом только в одной точке? Можно же принять в нескольких разных точках, где у компонент будут разные фазы и интенсивности.

-- 22.03.2026, 23:27 --

Есть ещё такая задача: Signal separation
И для неё есть разные решения.

[CSV3]

zykov в сообщении #1720893 писал(а):

CSV3 в сообщении #1720888 писал(а):

Стоит множество маяков, которые всенаправленно генерируют одну и ту же структурированную посылку, и в результате временных сдвигов и весьма высокой изотропности этой сети получатель принимает все это как псевдошум/шум

Ну они не просто складываются, а складываются с разными весами, т.к. находятся на разном расстоянии и будут иметь разную интенсивность в принимающей точке.
Кроме того, зачем ограничиваться сигналом только в одной точке? Можно же принять в нескольких разных точках, где у компонент будут разные фазы и интенсивности.

-- 22.03.2026, 23:27 --

Есть ещё такая задача: Signal separation
И для неё есть разные решения.

Да, конечно, если следовать моей аналогии, то возникнут веса. Да и вообще можно попытаться приблизиться к одному из маяков - и проблема во многом будет решена. Но я дал упрощенное сравнение, а для строгого мне пришлось бы разворачивать здесь ту самую теорию, что есть офтоп, да я и не стремлюсь к этому. Скажу лишь, что исходное определение задачи в первом посте - более строгое. Что касается статьи по ссылке - то по голосам там все сильно проще, ибо речь человека с 60х изучена вдоль и поперек - статистически, спектрально, фонемно, на этом были построены алгоритмы CELP и LD-CELP в системах связи, кои мне хорошо известны - кодировал в AD 21xx, как и другие, более углубленные. В двумерной области (изображения) тоже попроще, ибо мы знаем свои объекты, доступные нам зрением. В моей же задаче мы не знаем ничего о принципе формирования сигнала, и есть гипотеза, что он являет собой разновидность ПСП в нашем понимании. Есть дополнительная гипотеза, что аналитическое выражение каким-то образом связано фундаментально с известными нам рядами, вроде Фибоначчи, простых чисел или загадочном метании чисел до 1 в проблеме Коллатца. Однако на первом этапе получение некоей субстроки, которая будет заметно коррелировать с P - уже хорошо. Вот есть уже мнение, что шансов нет ) Я не могу оценить это строго и формально, ибо не математик, человек не может знать все и даже четверть )