Простая задача, которая приводит к слишком большим для нашей Вселенной числам Quanta Magazine

Оригинальное название: The Easy-Sounding Problem That Yields Numbers Too Big for Our Universe Ссылка на оригинальное видео: Дата публикации оригинала: 8 марта 2024 г. Переведенное описание: Как программист может гарантировать, что критически важная часть программного обеспечения не содержит ошибок? Ученые-теоретики-компьютерщики используют фундаментальный вопрос, называемый проблемой достижимости, который определяет, достигнет ли компьютер различных опасных состояний при запуске программы или избежит их. Чтобы лучше понять сложность проблемы, исследователи обратились к математическому инструменту, называемому системами сложения векторов. Благодаря серии недавних открытий ученые-компьютерщики установили, что сложность проблемы достижимости для систем сложения векторов определяется знаменитой функцией, называемой функцией Аккермана, которая становится чрезвычайно сложной даже при небольших входных данных. ---------- Прочтите полную статью, где есть ссылки на статьи: ИСПРАВЛЕНИЕ: 13 марта 2024 г. Примерно в то же время, что и статья Червинского и Орликовского 2021 года, в которой была повышена нижняя граница Леру и верхняя граница Аккермана Шмитца, Леру получил эквивалентный результат, работая независимо. Обе статьи доказали один и тот же нижний предел, и команды договорились опубликовать их одновременно. Ссылки на их работы можно найти здесь: - Проблема достижимости сетей Петри не является примитивно-рекурсивной, Леру - Достижимость в системах сложения векторов является полной по Аккерману, Червинскому и Орликовскому ---------- Главы: 00:00 Как формальная проверка находит ошибки в программировании 00:59 Проблема достижимости 01:41 Истоки параллельных вычислений и связанные с этим проблемы 02:40 Системы сложения векторов (васс) и проблема достижимости 04:16 В поисках сложности задачи, какой алгоритм самый быстрый? 04:38 Идентификация нижней и верхней границ проблемы достижимости 06:18 Объяснение функции Аккермана 07:32 Найдено окончательное решение проблемы достижимости Васы ---------- - ПОСЕТИТЕ наш сайт: - ПОСТАВЬТЕ нам НРАВИТСЯ на Facebook: - СЛЕДУЙТЕ за нами в Твиттере: Журнал Quanta — редакционно независимое издание, поддерживаемое Фондом Саймонса: