18+
Поздравления
Поздравляем
РА
РА
GX
GX
ingusha
ingusha
Eva
Eva

Coder - Lever. Энтропия в информатике.

Встречи, фотоотчеты, обсуждения встреч. Города, Республики, Страны. Наши совместные наработки.

Модераторы: Lever, навигатор, DK

Куратор темы: Lever

Coder - Lever. Энтропия в информатике.

Сообщение Lever » 08 окт 2015, 13:01

[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: тогда твой Вычислитель зациклится
не сможет вычислить колмогоровскую сложность данной ему строки
перебор остановится на первой запущенной пробной программе, которая зациклилась.
и вот колмогоровская сложность и энтропия (в информатике) - это уже очень близкие понятия.
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение DK » 08 окт 2015, 13:16

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

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

Кроме того еще по моему в этом доказательстве есть такая ошибка - когда мы говорим что программа запускает анализатор - почему мы предполагаем что она запускает именно ЭТОТ анализатор а не его копию? Если допустим программа запускает копию анализатора - то внешний анализатор может давать ответы совсем не такие как тот который запускается в программе - и тогда никакого противоречия не возникает. Если же мы поставим обязательное условие чтобы программа запускала именно ЭТОТ анализатор то тогда речь идет о слишком уж специфичной программе (и кроме того такое условие не оговорено изначально - т.е. не является обязательным) - одной из всех. И то что невозможно сделать ответ именно по этой программе еще ничего не говорит о том можно ли сделать ответ по любым другим.
Правильные выборы в каждый момент - путь к счастью.
Власть живой души - добро. Власть формальной механистичности - зло.
Аватара пользователя
DK
****************
****************
 
Сообщения: 11399
Зарегистрирован:
17 дек 2005, 00:23

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 08 окт 2015, 14:12

DK писал(а):По моему в доказательстве есть ошибка.

Да, я понял твою логику, и тоже сейчас засомневался.
Надо будет побеседовать с оппонентом, когда он появится, чтобы прояснить этот момент.
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение DK » 08 окт 2015, 14:42

Да, интересно обсудить с Кодером.
Правильные выборы в каждый момент - путь к счастью.
Власть живой души - добро. Власть формальной механистичности - зло.
Аватара пользователя
DK
****************
****************
 
Сообщения: 11399
Зарегистрирован:
17 дек 2005, 00:23

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 21 окт 2017, 06:56

go topchik
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 21 окт 2017, 06:59

Да, в доказательстве ошибка. (Андрей.)
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение КриоГен » 21 окт 2017, 15:45

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

http://synset.com/wiki/index.php/%D0%9F ... 1%82%D0%B8
КриоГен
**********
**********
 
Сообщения: 882
Зарегистрирован:
14 май 2017, 06:31

Re: Coder - Lever. Энтропия в информатике.

Сообщение КриоГен » 21 окт 2017, 16:26

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

Причём, заметьте, что нам нет необходимости заранее знать какой объём памяти потребуется алгоритму. Мы можем запоминать состояние только тех ячеек, в которые алгоритм писал. В процессе работы алгоритм будет менять своё состояние и либо закончит работу, либо состояния начнут повторяться (и мы это сразу заметим) либо алгоритм начнёт расширять свою память, чтобы расширить множество возможных неповторяющихся состояний. Чтобы алгоритм зациклился и мы этого не заметили, алгоритм будет вынужден расширять свою память бесконечно (т.е. писать всё в новые и новые ячейки).
КриоГен
**********
**********
 
Сообщения: 882
Зарегистрирован:
14 май 2017, 06:31

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 22 окт 2017, 01:51

Благо-дарю
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 22 окт 2017, 06:48

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

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

КриоГен, О Боже, - это очень красиво!
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье

Re: Coder - Lever. Энтропия в информатике.

Сообщение Lever » 22 окт 2017, 06:49

Хакеры Wins!

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

Продолжение здесь:
viewtopic.php?f=135&t=12320
Аватара пользователя
Lever
****************
****************
 
Сообщения: 5852
Зарегистрирован:
16 окт 2006, 13:02
Откуда: Чехов, Подмосковье


  • Похожие темы
    Комментарии
    Просмотры
    Последнее сообщение

Вернуться в ВСТРЕЧИ ЕДИНОМЫШЛЕННИКОВ

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron