?

Log in

No account? Create an account
dibr
 
[Most Recent Entries] [Calendar View] [Friends View]

Thursday, September 28th, 2017

Time Event
7:53p
О границах познаваемого
Оригинал взят у vadim_proskurin в О границах познаваемого


В позапрошлом веке философы спорили, познаваем ли мир, и если да, то до какой степени. Сейчас любому образованному человеку известно, что мир непознаваем, существуют достоверно неразрешимые задачи, например, задача остановки произвольной машины Тьюринга. Соответствующая теорема имеет простое следствие: существует конкретная машина Тьюринга (например, универсальная машина Тьюринга), для которой эта задача неразрешима. Другими словами, существует конкретный математический объект, для которого строго доказано, что некоторые его свойства непознаваемы.

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

В прошлом году некий Adam Yedidia (на фото), аспирант из MIT, построил конкретную машину Тьюринга из 7918 состояний, для которой доказал, что задача ее остановки неразрешима в рамках общепринятой теории множеств. Другими словами, предъявлен конкретный непознаваемый объект, и он оказался вовсе не астрономически сложным, его заархивированное описание занимает всего 8.5М.

Предвижу нашествие гуманитариев в комментах

9:00p
программистское
«FYI: компутеp с NTFS на Workstation пpи каких-то условиях способен залезть в холодильник и съесть все сосиски»
(c) Yaroslav Fedorov, in RU.OS.CMP, 1996

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

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

https://habrahabr.ru/company/infopulse/blog/338812/
(via https://vk.com/wall64593703_1483)

Вкратце.
Создаём статический внешний (т.е. видимый только для функций, описанных в этом же файле) указатель на функцию. Делаем функцию, в которой этому указателю присваивается адрес функции, залазящей в холодильник и съедающей все сосиски. ЭТУ ФУНКЦИЮ НИГДЕ НЕ ИСПОЛЬЗУЕМ. В основной программе не делаем ничего, просто вызываем функцию, адресуемую указателем.
С точки зрения здравого смысла и бытовой логики, указатель инициализируется значением NULL, его значение нигде не изменяется, значит попытка его использовать - это использование указателя NULL, и программа почти наверняка вылетит с экспешном (ошибкой выполнения) "вы тут NULL использовали, так нельзя".
С точки зрения же глубоко оптимизирующего компилятора всё не так просто. Компилятор видит, что указатель статический, то есть виден (и может быть изменён) только из этого файла. Изначально указатель инициализирован NULL, но есть функция, которая заносит в него адрес функции "съесть все сосиски", поэтому в принципе в указателе может оказаться и это значение (что функция, заносящая адрес, не вызывается из основной программы, ещё ничего не значит - её могут вызвать из соседнего модуля, она-то видна всем). Других значений в указатель не заносится, а значит на момент использования указателя в нём может быть одно из двух значений: или NULL, или "съесть все сосиски". В случае "съесть все сосиски" нужно съесть все сосиски, в случае же NULL можно делать всё что угодно... а значит для оптимизации кода - можно тоже съесть все сосиски! Сэкономим на указателе, заменим его константой. При этом в выполняемый код функция, заносящая в указатель значение "съесть все сосиски", может вообще не попасть - её ведь не вызывают, значит линковщик выбросит её как ненужную.

И есть компилятор, который так и делает.

Хотя по здравому смыслу - не должен.

Но стандарту тем не менее - не противоречит.

Где, говорите, живёт Сара Коннор?

<< Previous Day 2017/09/28
[Calendar]
Next Day >>
My Website   About LiveJournal.com