Энтропия в информатике. Проблема обратимости.

[Andrew Lever]

[0:59:17] Coder: раз уж речь зашла об энтропии в информатике
ты что-нибудь слышал о так называемой "проблеме остановки" (halting problem)?
[0:59:39] Lever: поясни чуток
что-то не припомню сходу
в чём она?
[1:03:07] Coder: в общем, ты в курсе, что некоторые программы работают и потом завершаются, выводя какие-то результаты, или падают с ошибкой, но так или иначе - они завершаются
а есть другие программы, которые не завершаются - зацикливаются.
и вот стоит задача - имея на руках текст программы, определить, зациклится она или нет.
[1:03:57] Lever: ну смотри
наверное это относится к старым языкам процедурного типа?
[1:04:17] Coder: да к любым
дополнительное условие - анализ должен проводить не человек, а программа Анализатор
[1:05:26] Coder: объясню другими словами
задача - написать программу, которая будет анализировать другие программы, написанные на заданном языке, на предмет того, зациклятся они или нет.
[1:06:52] Coder: для простоты считай, что программа консольная, однопотоковая
хоть на ассемблере Z80
где все процессы, происходящие в системе, под контролем
а сам ассемблер всяко легче поддается машинному анализу, чем ЯВУ
[1:07:36] Lever: надо прогонять как ИДОй
IDA Pro
она же анализирует
[1:07:55] Coder: да...
В общем, есть теорема,
которая утверждает, что эта задача не имеет решения.
[1:08:36] Lever: гм )
в общем случае (т.е. такого решения, которое бы работало на любых программах)
[1:08:55] Lever: и почему?
[1:09:18] Coder: даже в наиболее легкой обстановке, т.е. в случае какого-нибудь ассемблера на микроконтроллере или консольного однопоточного приложения хотя бы на бейсике
почему?
[1:09:30] Coder: ну, доказательство интересное и красивое
Доказательство от противного.
Допустим, что Анализатор существует (т.е. такая программа, которой можно скормить любую программу, и Анализатор определит, зацикливается анализируемая программа или нет, и при этом не зациклится сам).
Напишем тестовую программу, которая вызовет Анализатор сама на себе и в зависимости от результата, возвращенного Анализатором, зациклится или наоборот, завершится.
Причем таким образом, чтобы если Анализатор ответит, что тест-программа не зациклится - то она бы зациклилась, и наоборот.
Получим программу, результат исполнения Анализатора на которой заведомо ложный.
Ну или Анализатор зациклится
А это противоречит предположению, что Анализатор существует.
Следовательно, он не существует.
[1:13:03] Lever: а если прога на бейсике а анализатор на машинном коде?
Ну, переписать Анализатор на бейсике, либо прогу в машкоде
привести обе программы к одному языку, который понимает Анализатор
[1:15:14] Lever: а я немного не пойму как это сама на себе
то есть эта прога должна иметь и знать весь код анализатора?
[1:16:03] Coder: Ну вот представь, у тебя есть Анализатор, реализованный в виде функции на паскале или на си, ему на вход передается текст анализируемой программы со всеми ее зависимостями, а на выходе логическое значение - да или нет.
И наша тест-прога будет короткой, типа того (test.c)
void main(void)
{
BOOL r = Analyzer("main.c");
if(r)
return;
else
for(;;);
}
а перед текстом функции main() в файле main.c будет размещаться текст функции Analyzer, просто скопированный из файла Analyzer.c
Analyzer возвращает TRUE, если программа зацикливается, и FALSE - если завершается. Кроме того, Analyzer сам не зацикливается.
[1:20:56] Lever: ну я понял
смысл в том, что анализатор не может анализировать сам себя
[1:21:23] Coder: почему не сможет?
[1:21:28] Lever: тут любой бы зациклился )
[1:21:46] Coder: ну а как Анализатор вообще определит, себя он анализирует или нет?
можно же применить эквивалентные преобразования
поменять имена переменных, структуры данных, структуру программы
а логику сохранить
[1:22:11] Lever: да, интересно
[1:22:12] Coder: и все равно контр-пример будет работать
т.е. если бы вообще существовала такая логика, которая позволяла бы анализировать любую программу на предмет зацикливания
то и саму себя она и подавно смогла бы анализировать
[1:23:37] Lever: ну вообще это теория
реально я не представляю кто будет писать такую сложную вещь
[1:24:04] Coder: более того
это лишь базовая теорема
а на ее основе доказываются многие другие теоремы
которые играют большую роль в информатике
[1:25:22] Coder: так, например, исходя из того, что Анализатор не существует, следует то, что не существуют и анализаторы любых других свойств программ (не только на предмет зацикливания)
[1:25:33] Lever: я понял что получится
если запустить такой пример, он будет просто анализировать бесконечное время
[1:25:59] Coder: т.е. зациклится
а по условию не должен
или может не зациклиться, а вернуть ответ, который окажется неверным - и снова получим то, что Анализатор нарушает условия, которые он гарантирует (т.е. незацикливание и верный результат)
[1:27:32] Lever: ну а практически что это нам даёт или не даёт ?
[1:27:51] Coder: кстати
сам пример может, к примеру, всегда зацикливаться - это не страшно. Ведь это лишь пример, а не сам Анализатор.
Но мы ведь можем отдельно запустить Анализатор на тест-программе
и тогда он должен вернуть верный результат и не зациклится. Но как он это сделает, если это одна и та же программа фактически (фрагмент), вызванный с одними и теми же исходными данными?
[1:30:01] Coder: а практически - куча последствий
ну просто очень много
почти вся теория алгоритмов исходит из этой теоремы
вот еще одна вещь, тесно связанная с проблемой остановки
Задача - компрессия данных
причем с учетом размера декомпрессора
Бывает так, что данные сжаты хорошо, но декомпрессор большой, так что суммарный размер сжатых данных и декомпрессора может оказаться больше, чем суммарный размер данных, сжатых более плохим компрессором, но у которого имеется короткий декомпрессор.
[1:32:07] Lever: да
[1:32:17] Coder: В другой формулировке
Требуется найти программу минимальной длины, которая выдала бы на свой вывод заданную строку (т.е. интересующие нас декомпрессированные данные)
[1:33:16] Lever: это интересная задача
[1:33:25] Coder: при этом указанная программа, которую мы ищем, может иметь присоединенные к себе данные
главное и единственное требование - чтобы эта программа (вместе со вшитыми в нее данными) имела минимальную длину
очевидно, что такая программа существует
так как заведомо существует программа, способная выдать заданную строку, путем вшития этой строки в программу без всяких изменений и компрессии, а сама программа будет состоять из тривиальной операции вывода этой строки
раз существует одна программа - то существует и много их, какие-то короче, какие-то длиннее
и среди них есть одна, имеющая минимальную длину (в заданном языке программирования)
[1:36:20] Lever: ну от сжимаемости данных зависит конечно
[1:36:24] Coder: да.
[1:36:29] Lever: надо их проанализировать
[1:36:42] Coder: Ну вот.
Значит, мы имеем вполне четко поставленную задачу
1) есть строка, которую должна вывести искомая программа
2) существование и единственность искомой программы доказаны
3) требуется алгоритмически найти текст искомой программы (т.е. написать алгоритм, который находит искомую программу минимальной длины)
т.е. не человек ищет, а компьютер (под управлением Компрессора).
[1:38:39] Coder: Вариант попроще
3) требуется алгоритмически найти длину искомой программы (а не ее текст)
т.е. задача упрощается, нужно даже не найти текст программы минимальной длины, выводящей строку, а просто длину этой программы
[1:40:14] Lever: для одних данных?
[1:40:27] Coder: фактически мы каждой строке ставим в соответствие число - минимальную длину программы, которая может вывести эту строку
нет, конечно, для любых данных (любой строки)
[1:40:52] Lever: ну это очень сложно
[1:40:58] Coder: это не просто сложно
это невозможно
опять теорема
[1:41:22] Lever: там может и в бесконечность строки упереться
[1:41:37] Coder: Выше я упомянул, что в приведенных формулировках мы каждой строке ставим в соответствие число - длину мин. программы.
т.е. у каждой строки есть "нормальная" длина и есть эта хитрая "минимальная" длина.
Эта "минимальная длина" называется Колмогоровской сложностью строки.
[1:42:25] Lever: ух прикольно
[1:42:41] Coder: И есть теорема, что колмогоровскую сложность вычислить невозможно (т.е. не существует такого алгоритма, который мог бы ее вычислить)
ну для малых строк наверно нашли её
Да, возможно, для каких-то малых строк нашли.
Но в общем случае она неизвестна.
[1:43:57] Coder: Т.е. неизвестен предел сжатия строки
я могу тебе передать, допустим, длинный файл, выглядящий как случайный шум
ты применишь на нем все известные тебе компрессоры и обломаешься - сжать не сможешь
[1:44:41] Lever: ну на то лучшие умы и соревнуются
[1:44:42] Coder: а я тебе пришлю короткую прогу, которая создает этот файл
а прога эта, допустим, шифрует набор нулей известным мне секретным ключом по одному из сильных алгоритмов шифрования
[1:45:54] Lever: ого, прикольно
[1:45:57] Coder: т.е. для воспроизведения строки нужно знать секретный ключ шифра и сам алгоритм шифра и еще мой алгоритм, что именно я шифрую (набор нулей или арифметическую прогрессию или еще что-то)
[1:46:50] Lever: тут уже проблема обратимости какая-то
[1:46:07] Coder: и вот если бы существовала программа, вычисляющая колмогоровскую сложность
то она бы прошарила, что мой файл можно создать таким образом
и ты бы сразу увидел, что хоть файл и выглядит "страшно", но его можно сильно ужать.
[1:47:19] Lever: я хотел бы конечно в криптографии и криптографической математике побольше разбираться
но это глубокая тема
[1:47:28] Coder: тут криптография просто как пример
показывающий, что даже большой файл с "шумом" может иметь малую колмогоровскую сложность
по крайней мере не выше, чем длина моей (неизвестной тебе) программы, с помощью которой я создал этот файл
[1:48:10] Lever: да, очень занимательно
[1:48:21] Coder: а доказательство тоже красивое
(что алгоритма, вычисляющего колмогоровскую сложность произвольной строки, не существует)
так вот. Доказательство.
Допустим, что алгоритм, верно вычисляющий колмогоровскую сложность для любой строки, существует.
назовем его Вычислитель.
Составим цикл, перебирающий все строки подряд, и вызввающий на них Вычислитель.
Как только получим результат вычисления, который превышает некое число N, которое больше, чем длина Вычислителя с добавкой к нему нашего алгоритма - выведем эту строку на экран.
В результате получится, что наш алгоритм, имеющий (вместе с Вычислителем) длину N, выведет на экран строку, колмогоровская сложность которой превышает N.
что противоречит условию теоремы.
Следовательно, Вычислитель не существует.
[1:58:42] Lever: я немного не понял
ведь нам надо будет ещё прикрепить очень сложную строку
[1:59:20] Coder: ну т.е. вычислитель сообщит нам, что колм. сложность строки (т.е. минимальная длина программы, выводящей на экран эту строку), составляет M, M>N
А наш алгоритм имеет длину N и тоже выведет эту строку
не надо ее крепить, она сама получится в результате перебора.
[2:00:21] Lever: всё только что понял
то есть типа как генерировать белый шум
[2:01:18] Coder: конечно, это будет долго работать, но рано или поздно сработает. Понятие колмогоровской сложности учитывает только длину алгоритма, а не время его работы. Самый короткий алгоритм вывода строки не обязан быть самым быстрым.
[2:02:11] Lever: а как перебирать?
[2:02:14] Coder: подряд
как пароли перебираешь
сначала рассматриваешь все строки длины 1, все символы из набора
потом строки длины 2 со всеми комбинациями из 2 символов
и т.д.
[2:02:55] Lever: да, прикольно
эти 2 вещи очень похожи
они по типу "сможет ли Бог сотворить камень, который не сможет поднять"
тоже ведь ответа нет
[2:04:05] Coder: ну да, где-то похоже
а вот еще
связь колмогоровской сложности и проблемы остановки
если бы существовал Анализатор, то можно было бы составить и Вычислитель
который бы просто перебирал все программы подряд, анализировал их (с помощью Анализатора) на предмет зацикливания и запускал бы те, которые не зацикливаются
по завершению - анализировал бы вывод. Если он совпадает с входной строкой - то возвращал бы длину программы, которая ее выводит.
но Анализатора не существует, а запускать любую программу нельзя, вдруг она зациклится.
[2:07:25] Lever: я не понял а какие программы и почему они могут зациклиться?
программа генерирующая белый шум?
[2:08:01] Coder: все программы можно перебрать подряд, начиная от коротких
тем же способом, как ты перебираешь пароли
долго, но можно
[2:08:36] Lever: а, идею понял
[2:08:42] Coder: и вот ты перебираешь все программы и запускаешь те из них, которые не зацикливаются
по завершении их (т.к. они не зацикливаются) смотришь, что они вывели на экран
если нашлась программа, которая вывела то, что тебе нужно - то она есть искомая минимальной длины
[2:09:28] Lever: да, теоретики приколисты )))
типа перебираешь случайную хрень бац а это искомая прога
[2:10:27] Coder: совершенно верно
[2:10:33] Lever: да ещё и уникальная в своём роде
[2:10:36] Coder: но тут проблема - программа может зациклиться.
а проверить заранее, зациклится она или нет, ты не можешь.
[2:11:19] Lever: то есть если она зациклится - вообще ничего не выведет?
результата не будет
[2:11:28] Coder: тогда твой Вычислитель зациклится
не сможет вычислить колмогоровскую сложность данной ему строки
перебор остановится на первой запущенной пробной программе, которая зациклилась.
и вот колмогоровская сложность и энтропия (в информатике) - это уже очень близкие понятия.

[DK]

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

По моему в доказательстве есть ошибка. Нам нужно чтобы анализатор анализировал любую программу а не только программу которая сама запускает анализатор. Да - это доказательство показывает что невозможно проанализировать программу которая сама запускает этот же анализатор. Но это доказательство ничего не говорит о возможности проанализировать другие программы - которые не запускают этот анализатор.

Кроме того еще по моему в этом доказательстве есть такая ошибка - когда мы говорим что программа запускает анализатор - почему мы предполагаем что она запускает именно ЭТОТ анализатор а не его копию? Если допустим программа запускает копию анализатора - то внешний анализатор может давать ответы совсем не такие как тот который запускается в программе - и тогда никакого противоречия не возникает. Если же мы поставим обязательное условие чтобы программа запускала именно ЭТОТ анализатор то тогда речь идет о слишком уж специфичной программе (и кроме того такое условие не оговорено изначально - т.е. не является обязательным) - одной из всех. И то что невозможно сделать ответ именно по этой программе еще ничего не говорит о том можно ли сделать ответ по любым другим.

[Andrew Lever]

По моему в доказательстве есть ошибка.

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

[DK]

Да, интересно обсудить с Кодером.

[Andrew Lever]

Да, в доказательстве ошибка. (Андрей.)

[КриоГен]

Вот тут неплохой разбор:

http://synset.com/wiki/index.php/%D0%9F ... 1%82%D0%B8

[КриоГен]

Вообще-то, для алгоритмов конечной длины, использующих конечный объём памяти для своих данных, проблема остановки разрешима.
Мы можем выполнять алгоритм пошагово и на каждом шаге запоминать его состояние (всю его область памяти и адрес текущей инструкции). Поскольку существует только конечный набор состояний, алгоритм либо остановится, либо состояния начнут повторяться. Как только мы заметим, что на некоторм шаге алгоритм попал в состояние, в котором уже был раньше, мы cможем сделать вывод, что алгоритм зациклился.

Причём, заметьте, что нам нет необходимости заранее знать какой объём памяти потребуется алгоритму. Мы можем запоминать состояние только тех ячеек, в которые алгоритм писал. В процессе работы алгоритм будет менять своё состояние и либо закончит работу, либо состояния начнут повторяться (и мы это сразу заметим) либо алгоритм начнёт расширять свою память, чтобы расширить множество возможных неповторяющихся состояний. Чтобы алгоритм зациклился и мы этого не заметили, алгоритм будет вынужден расширять свою память бесконечно (т.е. писать всё в новые и новые ячейки).

[Andrew Lever]

Благо-дарю

[Andrew Lever]

Вообще-то, для алгоритмов конечной длины, использующих конечный объём памяти для своих данных, проблема остановки разрешима.
Мы можем выполнять алгоритм пошагово и на каждом шаге запоминать его состояние (всю его область памяти и адрес текущей инструкции). Поскольку существует только конечный набор состояний, алгоритм либо остановится, либо состояния начнут повторяться. Как только мы заметим, что на некоторм шаге алгоритм попал в состояние, в котором уже был раньше, мы cможем сделать вывод, что алгоритм зациклился.

Причём, заметьте, что нам нет необходимости заранее знать какой объём памяти потребуется алгоритму. Мы можем запоминать состояние только тех ячеек, в которые алгоритм писал. В процессе работы алгоритм будет менять своё состояние и либо закончит работу, либо состояния начнут повторяться (и мы это сразу заметим) либо алгоритм начнёт расширять свою память, чтобы расширить множество возможных неповторяющихся состояний. Чтобы алгоритм зациклился и мы этого не заметили, алгоритм будет вынужден расширять свою память бесконечно (т.е. писать всё в новые и новые ячейки).

КриоГен, О Боже, - это очень красиво!

[Andrew Lever]

Хакеры Wins!

Но дальше будет чуть посложнее. О равенстве P и NP.

Продолжение здесь:
viewtopic.php?f=135&t=12320

[Andrew Lever]

[1:45:57] Coder: т.е. для воспроизведения строки нужно знать секретный ключ шифра и сам алгоритм шифра и еще мой алгоритм, что именно я шифрую (набор нулей или арифметическую прогрессию или еще что-то)
[1:46:50] Lever: тут уже проблема обратимости какая-то
[1:46:07] Coder: и вот если бы существовала программа, вычисляющая колмогоровскую сложность
то она бы прошарила, что мой файл можно создать таким образом
и ты бы сразу увидел, что хоть файл и выглядит "страшно", но его можно сильно ужать.

меня из всего диалога больше всего интересует вот этот кусок...
почему существующие архиваторы не способны вычислять колмогоровскую сложность... или хотя бы приблизиться к этому

белый шум vs "розовый" или "в поисках истинного ХАОСА" )))

[КриоГен]

Существующие архиваторы устраняют только некоторые типы упорядоченности. Обычно устраняется разная частота встречаемости символов и повторы подстрок. Упакованный файл будет выглядеть, как шум. В нём все символы будут встречаться одинаковое кол-во раз. И дальше он упаковываться не будет, так как в нём нет этого типа упорядоченности. Но в нём могут быть другие типы упорядоченности, на которые архиватор не рассчитан.
Хороший псевдослучайный генератор выдаст тебе массив чисел, который тоже будет похож на шум и не будет упаковываться существующими архиваторами. В то же время, есть алгоритм генератора, который этот массив породил. И алгоритм может быть очень коротким, но порождать длинные последовательности. Фактически, можно сказать, что массив псевдослучайных чисел имеет очень большой скрытый порядок. Но ключ к этому порядку - алгоритм генератора - мы не можем найти.
Да, мы можем начать перебирать все возможные алгоритмы, но у нас есть проблема остановки. Если очередной проверяемый алгоритм зациклится, то мы будем ждать его завершения вечно. Это теоретически.
А практически у нас не хватит мощностей, чтобы организовать даже сильно урезанный перебор.

Мне почему-то кажется, что мы это уже когда-то обсуждали...

[Andrew Lever]

Теоретически любые шифры поддаются дешифрованию.
Пригожин в физике ввёл постулат об энтропийном барьере.
Что является его аналогом в информатике?

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

https://ru.wikipedia.org/wiki/Факторизация_целых_чисел

Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.

В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно "сложной" задачей.

В марте 1994 года с помощью двойной вариации множественного полиномиального QS командой математиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. Вычисления выполнялись добровольцами в Internet - в течение восьми месяцев трудились 600 человек и 1600 компьютеров, возможно, самый большой в истории многопроцессорный конгломерат. Трудоемкость вычислений была в диапазоне от 4000 до 6000 mips-лет. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использовались QS и теория пятилетней давности, NFS мог бы ускорить выполнение расчетов раз в десять. В соответствии с: "Мы делаем вывод, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев." По оценкам авторов разложение 512-битового числа в 100 раз более трудоемко при использовании той же техники и только в 10 сложнее при использовании NFS и современной техники.

Стойкость алгоритма шифрования ГОСТ 2012 основывается на проблеме дискретного логарифмирования в группе точек эллиптической кривой. На данный момент нет метода решения данной проблемы хотя бы с субэкспоненциальной сложностью.

Зачем возиться с эллиптическими кривыми, если RSA и так работает хорошо?

Простой ответ дал NIST, представив таблицу сравнения размеров ключей RSA и ECC, необходимых для получения одинакового уровня защиты.

Код: Выделить всё

Размер ключа RSA (биты)   Размер ключа ECC (биты)
       1024                         160
       2048                         224
       3072                         256
       7680                         384
       15360                        521

Заметьте, что линейной связи между размерами ключей RSA и ECC нет (другими словами: если мы удваиваем размер ключа RSA, нам не нужно удваивать размер ключа ECC). Таблица говорит нам, что ECC не только использует меньше памяти, но и генерирование ключей с подписыванием в ней гораздо быстрее.

https://habr.com/ru/post/335906/

Метод Полларда был использован в апреле 2000 г. для решения задачи дискретного логарифмирования в группе точек эллиптической кривой
y^2 + xy = x^3 + x^2 + 1
над полем GF(2^109), порядок которой равен 324518553658426701487448656461467 (108 бит), в рамках организованного группой французских специалистов международного проекта. Задача была решена за 4 месяца с помощью 9500 компьютеров с использованием ресурсов Интернета. Заметим, что выполненного объема вычислений хватило бы для решения 50 задач факторизации 512-битовых чисел. Для решения аналогичной задачи в поле GF(2^163) с использованием той же вычислительной техники и точно такого же алгоритма потребовалось бы примерно 40 000 000 лет. Этот пример отлично иллюстрирует разницу между алгоритмами экспоненциальной и субэкспоненциальной сложности.

Все попытки создания субэкспоненцальных алгоритмов для эллиптических кривых закончились неудачей и тому есть серьезные причины. Дело в том, что при создании алгоритмов субэкспоннциальной сложности исходная группа вкладывается в кольцо, в котором существует много малых простых элементов. Например, в субэкспоненциальном алгоритме вычисления дискретного логарифма в мультипликативной группе простого поля существенно используется тот факт, что случайное целое число с достаточно большой вероятностью можно разложить на простые множители небольшого размера. Аналогичным свойством обладают и целые алгебраические числа, где существует богатый набор целых простых алгебраических чисел, имеющих небольшую норму, а также кольцо многочленов над конечным полем, где достаточно много неприводимых многочленов небольшой степени. На эллиптических кривых точек с такими свойствами нет. Этот факт Нил Коблиц назвал золотым щитом, оберегающим эллиптическую криптографию.

http://textarchive.ru/c-1424393.html

[Andrew Lever]

КриоГен, да, хороший пост твой, во всём понятный.

Я тут просто сетую, что современные архиваторы не могут пожать файл до колмогоровской сложности, и немного пытаюсь вникнуть, почему, что является теоретическим препятствием к этому.

Кстати, никак в данный момент не найду в поисковиках материал о репаках и пересжатии формата JPG чуть ли не на 50% укорачивания с тем же качеством. Так вот, этот комплект шёл парой, сначала распаковщик JPG (одна прога), а потом упаковщик (другая прога). К сож, забыл и где я это видел и форматы. То ли к тотал коммандеру какие-то плагины были, то ли когда WebP изучал, гуглил.

И в чём самая фишка: сжатый JPG ничем ужать нельзя, а вот зная ключ распаковки - можно и намного.

[КриоГен]

Попробуй вот эту штуку:
https://riot-optimizer.com/

Но jpeg всё равно сжимается с потерями. Пусть эти потери и незаметны.

[Andrew Lever]

https://nplus1.ru/news/2019/10/25/entropy-compression

Энтропию системы связали со степенью сжатия информации

Физики из Университета Тель-Авива разработали метод, с помощью которого можно быстро и точно оценить энтропию системы, не прибегая к дополнительным соображениям. Для этого исследователи отображали систему в одномерную строку, рассчитывали степень, до которой ее можно сжать без потерь, и отображали полученное значение в энтропию. На пяти модельных примерах, в которых энтропию можно рассчитать точно, погрешность алгоритма не превышала нескольких процентов. Кроме того, ученые показали, что с помощью предложенного алгоритма можно решать задачу фолдинга белков. Статья опубликована в Physical Review Letters.

Чтобы ухватить основные термодинамические свойства системы, достаточно знать две функции — энтропию и энтальпию системы. Грубо говоря, энтропия измеряет упорядоченность элементов системы, а энтальпия — энергию, которая необходима для поддержания ее структуры. Чтобы оценить энтальпию, достаточно знать силу взаимодействия между компонентами системы, поэтому с вычислением этой функции обычно проблем не возникает. В то же время, для вычисления энтропии необходимо найти вероятности, с которыми реализуются все возможные микросостояния системы (например, различные способы сворачивания белка). С увеличением размера системы сложность этой задачи быстро растет, и для больших систем ее не могут решить даже современные суперкомпьютеры. Чтобы оценить свойства таких систем, ученым приходится идти на ухищрения.

В частности, один из способов оценить энтропию сложной системы основан на использовании некоторых априорных знаний и предположений — например, эмпирических данных, накопленных в экспериментах с похожими системами. Это позволяет «урезать» пространство, которое нужно смоделировать компьютеру. К сожалению, для каждой задачи способ «урезания» разный. Другие алгоритмы полагаются на методы, которые оценивают распределение работы в ходе вычисления или рассматривают отношения между различными областями фазового пространства. Впрочем, в этих методах также нельзя выделить явного лидера, и во многих случаях эффективность их работы также сильно зависит от поставленной задачи.

Группа исследователей под руководством Рой Бека (Roy Beck) разработала алгоритм, который довольно точно оценивает асимптотическую энтропию произвольной системы, но требует сравнительно мало вычислений. Для этого ученые заметили, что энтропия системы пропорциональна степени, до которой можно без потерь сжать строку символов, полностью описывающую заданную конфигурацию. Грубо говоря, чем больше энтропия системы, тем сложнее в ней выделить какие-либо закономерности; если же таких закономерностей нет, «ужать» информацию о системе без потерь невозможно. Осталось придумать, как корректно отобразить в строку систему, которая в общем случае описывается большим числом непрерывных степеней свободы.

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

После этого полученный одномерный массив чисел исследователи сжимали без потерь с помощью алгоритма Лемпеля — Зива — Велча, реализованного в программе 7-Zip. Если кратко, то этот алгоритм идет вдоль цепочки символов и ищет повторяющиеся короткие отрезки, а затем заменяет их указателями на места, в которых он впервые столкнулся с такими отрезками. Наконец, ученые рассчитывали степень сжатия массива и отображали ее в энтропию системы. В качестве первого приближения ученые использовали линейную функцию, в котором коэффициентом пропорциональности служит число степеней свободы, умноженное на логарифм от числа переменных, необходимых для описания каждой степени свободы по отдельности. Справедливость этого приближения ученые доказали на конкретных примерах.

Для проверки предложенного метода физики рассмотрели пять систем, для которых энтропию можно рассчитать аналитически. Во-первых, ученые нашли энтропию четырехуровневой системы при разной температуре. Во-вторых, физики рассмотрели двумерную модель Изинга на квадратной решетке, которая описывала ферромагнетик или фрустрированный антиферромагнетик. В-третьих, исследователи повторили расчеты для модели Изинга на треугольной решетке. Наконец, ученые оценили энтропию цепочки из N звеньев, конец и начало которой разнесены на фиксированное расстояние. Во всех этих случаях полученная энтропия отличалась от точного значения всего на несколько процентов (не считая постоянного сдвига).

Сравнение энтропии, рассчитанной алгоритмом для разных температур, с точной энтропией для четырехуровневой системы (a), модели Изинга на квадратной решетке (b), модели Изинга на треугольной решетке (c) и цепочки с фиксированными концами (d)

Наконец, ученые, вдохновленные успехами алгоритма на модельных примерах, попытались решить задачу фолдинга белка (чтобы узнать, как свернется белок, нужно найти конфигурацию с наименьшей конфигурационной энтропией). В качестве примера физики рассмотрели C-концевой участок виллина. С помощью предложенного алгоритма исследователи построили h,s-диаграмму (enthalpy-entropy population diagram), которая позволяла отличить свернутые и развернутые состояния с точностью около 95 процентов. Ученые подчеркивают, что для оценки «свернутости» им не пришлось использовать какие-то дополнительные соображения о строении белка.

Интересно, что препринт статьи авторы выложили еще в сентябре 2017 года, а в журнал отправили в мае 2018. Таким образом, статья рецензировалась почти полтора года. Впрочем, процитировали ее за это время всего один раз.

Один из необычных примеров энтропии — это энтропия запутывания, которая определяется как обычная энтропия для «урезанной» квантовой системы. С помощью этой величины можно оценивать степень квантовой запутанности двух систем — например, частиц, которые рождаются в динамическом эффекте Казимира или упруго рассеиваются друг на друге. Некоторые физики даже считают, что с помощью энтропии запутывания можно понять, как устроены квантовые состояния черной дыры.

Дмитрий Трунин

[Andrew Lever]

Простыми словами о факторизации натуральных чисел:
https://zen.yandex.ru/media/mathematic/ ... 7816a53d77

Но jpeg всё равно сжимается с потерями. Пусть эти потери и незаметны.

Это я знаю, видел и ухудшение своими глазами. И качество сжатия жпег настраивается при сохранении. >Сжатие = >Ухудшение

[Andrew Lever]

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

По моему в доказательстве есть ошибка. Нам нужно чтобы анализатор анализировал любую программу а не только программу которая сама запускает анализатор. Да - это доказательство показывает что невозможно проанализировать программу которая сама запускает этот же анализатор. Но это доказательство ничего не говорит о возможности проанализировать другие программы - которые не запускают этот анализатор.

Кроме того еще по моему в этом доказательстве есть такая ошибка - когда мы говорим что программа запускает анализатор - почему мы предполагаем что она запускает именно ЭТОТ анализатор а не его копию? Если допустим программа запускает копию анализатора - то внешний анализатор может давать ответы совсем не такие как тот который запускается в программе - и тогда никакого противоречия не возникает. Если же мы поставим обязательное условие чтобы программа запускала именно ЭТОТ анализатор то тогда речь идет о слишком уж специфичной программе (и кроме того такое условие не оговорено изначально - т.е. не является обязательным) - одной из всех. И то что невозможно сделать ответ именно по этой программе еще ничего не говорит о том можно ли сделать ответ по любым другим.

Твой пост напоминает парадокс:
"Я всегда лгу" - который не даёт ответа на истинность этого высказывания.
Но если вторая копия говорит "Он [первая копия] всегда лжёт", то парадокс теряется.
Так и копии этого Вычислителя (Анализатора).
Так что суть уловил ты верно.