Прерывание в полевых условиях

Question

Когда вы когда-либо лично встречались с halting problem в поле? Это может быть, когда коллега/босс предложил решение, которое нарушило бы фундаментальные пределы вычислений, или когда вы поняли, что проблема, которую вы пытаетесь решить, на самом деле невозможно решить.

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

Answer 1

I буквально получил задание на остановку, как в «написать плагин монитора, чтобы определить, постоянно ли остановлен хост». Шутки в сторону? Хорошо, так что я просто дам ему порог. «Нет, потому что после этого он может вернуться».

Прошло много теоретической экспозиции.

Answer 2

Сложный статический анализ кода может столкнуться с проблемой остановки.

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

Answer 3

The project I'm working on right now имеет неразрешимые проблемы во всем этом. Это единичный тестовый генератор, поэтому, в общем, он пытается ответить на вопрос «Что делает эта программа». Что является примером проблемы с остановкой. Еще одна проблема, которая возникла во время разработки, - это . «Даны две (тестовые) функции«? Или даже "делает заказ этих двух вызовов (утверждений)"?

Что интересно об этом проекте является то, что, даже если вы не можете ответить на эти вопросы в всех ситуациях можно найти умные решения, решить проблему 90% времени, которое для этого домена на самом деле отлично.

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

Answer 4

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

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

Here's a particularly elaborate example.

Answer 5

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

Есть способы частично «разрешить» взаимоблокировки в сложной системе, наложив еще один слой поверх блокировки (например, определенный порядок получения), но эти методы не всегда применимы.

---

Почему это эквивалентно Проблема Остановки:

Представьте у вас есть два замка, A и B, и два потока, X и Y. Если поток X имеет блокировку A, и хотите заблокировать B также , а нить Y имеет блокировку B и хочет A тоже, тогда у вас есть тупик.

Если у X и Y есть доступ как к A, так и B, то единственный способ гарантировать, что вы никогда не попадете в плохое состояние, - это определить все возможные пути, которые каждый поток может принимать через код, и порядок, в котором они могут приобретать и удерживать блокировки во всех этих случаях. Затем вы определяете, могут ли два потока когда-либо приобретать более одной блокировки в другом порядке.

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

Answer 6

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

Поскольку завод был в полном объеме, консультант не смог запустить свое программное обеспечение в режиме реального времени, чтобы проверить его алгоритмы планирования. Вместо этого он написал симпатичный графический симулятор. Когда мы смотрели, как виртуальные поддоны перемещаются по его схеме на экране, я спросил: «Как вы узнаете, есть ли у вас какие-либо конфликты планирования?»

Его быстрый ответ: «Легко - симуляция никогда не прекратится».

Answer 7

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

Для приложения не существует API-интерфейсов для управления тем, как должен себя вести драйвер, или установить тайм-аут или что-то в этом роде, и, конечно же, водитель не может сказать, будет ли ваш шейдер завершен или нет.

Я не знаю, улучшилась ли эта ситуация в последнее время, но я хотел бы знать.

Answer 8

Я когда-то работал над проектом интеграции в банкомате (банкоматах).Клиент попросил меня создать отчет из моей системы для транзакций, отправленных переключателем страны, которые не были получены моей системой!

Answer 9

Пример 1. Сколько страниц в моем отчете?

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

Определение отчета оказалось настолько гибким, что оно было полным. Он может смотреть на переменные, выбирать между альтернативами, использовать циклы для повторения вещей.

Я определил встроенную переменную N, количество страниц в экземпляре отчета, поэтому вы можете поместить строку, на которой указана «страница n из N» на каждой странице. Я сделал два прохода, первый для подсчета страниц (в течение которых N был установлен на ноль), а второй - для их генерации, используя N, полученный с первого прохода.

Иногда первый проход будет вычислять N, а затем второй проход будет генерировать другое количество страниц (потому что теперь ненулевой N изменит то, что сделал отчет). Я пробовал делать итеративные действия до тех пор, пока N не успокоился. Тогда я понял, что это безнадежно, потому что, если он не успокоится?

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

Спустя годы я заметил, что MS Access иногда печатает «Страница 6 из 5», что является поистине чудесной вещью.

Пример 2: Составители С ++

Процесс компиляции включает в себя расширение шаблонов. Определения шаблонов могут быть выбраны из нескольких специализаций (достаточно хороших, чтобы служить «cond»), и они также могут быть рекурсивными. Таким образом, это полная мета-система Turing (чисто функциональная), в которой определениями шаблонов являются язык, типы - значения, а компилятор - действительно интерпретатор. Это был несчастный случай.

Следовательно, невозможно изучить любую данную C++-программу и сказать, может ли компилятор в принципе завершиться успешной компиляцией программы.

Поставщики компиляторов обойдутся этим, ограничив глубину стека рекурсивного шаблона. Вы можете настроить глубину в g ++.

Answer 10

«Как вы можете заверить меня, что ваш код на 100% свободен от ошибок?»

Answer 11

Несколько лет назад я помню, как читал обзор (в журнале Byte, я считаю) продукта под названием Basic Infinite Loop Finder или BILF. BILF должен был сканировать исходный код Microsoft Basic и найти любые петли, которые не завершались. Он утверждал, что сможет найти любые бесконечные циклы в коде.

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

В следующем выпуске опубликовано письмо представителя компании, в котором объясняется, что проблема будет исправлена ​​в следующем выпуске.

Обновление: Я столкнулся с изображением статьи на imgur. Я вспомнил неправильный журнал. Это был Creative Computing, а не Byte. В противном случае, я очень помню это.

Вы можете увидеть его версию hi-res на imgur.

Answer 12

От Functional Overview of (Eclipse) Visual Editor:

Затмение Visual Editor (VE) может быть использован для открытия любой .java файл. Затем он анализирует исходный код Java, смотря для визуальных компонентов. ...

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

Eclipse, VE, однако ... может быть либо используется для редактирования ГПИ с нуля, или из Java-файлов, которые были «жёстко» или встроенными в другом визуальном инструменте. Исходный файл может либо обновляться с использованием графического окна Viewer, дерева или свойств JavaBeans или можно редактировать непосредственно Редактор исходного кода.

Возможно, теперь я должен придерживаться Matisse.

Несвязанный, вот кто-то asking for проблема с остановкой внутри Eclipse.

Чтобы быть справедливым, область VE довольно ограничена, и, вероятно, это не сходит с ума из-за сложных вещей, таких как отражение. Тем не менее, требование построить GUI из любой java файл кажется halt-ish.

Answer 13

Я нашел бумагу Berkeley: Looper: Lightweight Обнаружение бесконечных циклов во время выполнения http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf

LOOPER может быть полезным, поскольку большинство бесконечных циклов тривиальные ошибки. Однако в этой статье даже не упоминается проблема с остановкой!

Что они говорят об их ограничениях?

[LOOPER], как правило, не может рассуждать о циклах, где незавершение зависит от особенностей мутации кучи в каждой итерации цикла. Это потому, что наше символическое исполнение является консервативным в конкретизирующих указателях, а наши символические рассуждения недостаточно мощным.Мы считаем, что объединение наших методов с анализом формы и более мощное генерирование инвариантов и доказательство будут ценными будущей работы.

Другими словами, «проблема будет исправлена ​​в следующей версии».