---
title: "Математика и вычисления · Симуляции · Гипотеза симуляции"
url: https://simulation-hypothesis.com/ru/simulations/mathematics-computation
description: "Числа, доказательства, графы и машины, исследуемые вычислением так же, как и выводом. Часть таксономии симуляций, которые люди действительно запускают."
license: https://creativecommons.org/licenses/by/4.0/
credit: "Ross Allan Dahl, Гипотеза симуляции (simulation-hypothesis.com)"
---

[Симуляции](https://simulation-hypothesis.com/ru/simulations)область 12 из 18

# Математика и вычисления

Числа, доказательства, графы и машины, исследуемые вычислением так же, как и выводом.

Математика и информатика теперь проверяют собственные идеи симуляцией. Они порождают миллионы случайных графов, чтобы увидеть, что типично. Запускают машину, чтобы увидеть, что алгоритм делает на самом деле. Раз за разом атакуют шифр, чтобы узнать, как он ломается. Ничто из этого не описывает физический мир. Это исследование самого пространства чисел, структур и вычислений. Практика тянется от экспериментальной математики, которую веками делали вручную, до современных средств верификации, проверяющих проект на каждое достижимое состояние ещё до его постройки.

## Чистая математика на компьютере

### Эксперименты со случайными матрицами

Большие матрицы, заполненные случайными числами, многократно диагонализуют, чтобы изучить статистику их собственных значений.

Вопрос, на который отвечает: В какую картину оседают собственные значения случайной матрицы и совпадает ли она с другими областями математики и физики?

Не учитывает: Всегда выбирает лишь крошечный уголок бесконечного пространства возможных матриц.

Работает на: около 10^12 FLOPS приблизительно университетский кластер, создающий и диагонализирующий множество больших матриц С: 1955 Ранняя работа Вигнера по статистике собственных значений случайных матриц

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### Эксперименты со случайными графами

Графы, построенные по случайному правилу, по одному узлу или по одному ребру, чтобы увидеть, какие свойства, например связность или кластеризация, встречаются как типичные.

Вопрос, на который отвечает: Как выглядит «типичная» сеть при таком правиле добавления узлов и рёбер?

Не учитывает: Настоящие сети редко бывают такими чистыми, как правило, порождающее модель.

Работает на: около 10^10 FLOPS приблизительно работает на настольном компьютере для графов до миллионов узлов С: 1959 Модель случайного графа Эрдёша и Реньи

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Сетевые модели](https://simulation-hypothesis.com/ru/simulations/methods#m-network)нижний уровень: Правила

### Симуляция перколяции

Решётку или сеть, где узлы или связи открываются случайно, наблюдают до момента, когда связный путь вдруг пронизывает всю систему.

Вопрос, на который отвечает: При какой плотности случайная сеть вдруг становится связной от края до края?

Не учитывает: Идеализированные решётки ведут себя чище любого настоящего пористого материала или сети.

Работает на: около 10^10 FLOPS приблизительно настольная машина для больших переборов параметров на решётке С: 1957 Введение теории перколяции Бродбентом и Хаммерсли

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Клеточные автоматы](https://simulation-hypothesis.com/ru/simulations/methods#m-cellular-automata)нижний уровень: Правила

### Поиски в экспериментальной математике

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

Вопрос, на который отвечает: Верна ли эта гипотеза для каждого случая, который кто-то способен проверить, и проступает ли закономерность?

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

Работает на: около 10^11 FLOPS приблизительно университетский кластер, работающий днями над одним поиском С: 1963 к 1963 году: компьютерный поиск целочисленных соотношений и закономерностей простых чисел

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Оценка констант методом Монте-Карло

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

Вопрос, на который отвечает: Насколько точно одно лишь слепое случайное сэмплирование может определить точную математическую величину?

Не учитывает: Сходится намного медленнее, чем почти любой более изощрённый численный метод.

Работает на: около 10^9 FLOPS приблизительно работает на ноутбуке за секунды или минуты С: 1946 Идея Улама 1946 года; фон Нейман предложил версию для электронного компьютера в марте 1947 года, а метод впервые опубликовали в 1949 [источник](https://mcnp-green.lanl.gov/pdf%5Ffiles/Article%5F1987%5FLAS%5FEckhardt%5F131--141.pdf) В дереве симуляций: [Метод Монте-Карло](https://simulation-hypothesis.com/ru/trees/simulations?n=m-montecarlo)

[Запустить интерактивную модель](https://simulation-hypothesis.com/ru/simulations/run#toy-pi)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### Вычислительные поиски в теории чисел

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

Вопрос, на который отвечает: Обладает ли это огромное число искомым свойством, и как далеко поиск может продвинуть рекорд?

Не учитывает: Поиски рекордов мало что говорят о числах, которые никто ещё не додумался проверить.

Работает на: около 10^13 FLOPS приблизительно проект добровольных распределённых вычислений на многих пожертвованных машинах С: 1951 Ручной тест Люка для простых чисел Мерсенна, впервые запущенный на компьютере в 1951 году

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### Численные методы для хаотических аттракторов

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

Вопрос, на который отвечает: Почему простая детерминированная система становится непредсказуемой?

Не учитывает: Из-за численного округления долгая траектория не настоящая орбита, а лишь такая, что остаётся близко к ней.

Работает на: около 10^3 FLOPS приблизительно несколько уравнений, секунды на ноутбуке. С: 1963 Детерминированное непериодическое течение Лоренца, модель конвекции, посчитанная на компьютере. [источник](https://doi.org/10.1175/1520-0469%281963%29020<0130:dnf>2.0.co;2) В дереве симуляций: [Хаотическая конвекция Лоренца](https://simulation-hypothesis.com/ru/trees/simulations?n=p-lorenz)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)нижний уровень: Правила

### Эксперименты с нелинейными решётками

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

Вопрос, на который отвечает: Распределяет ли нелинейная цепочка свою энергию поровну между всеми движениями?

Не учитывает: Результаты зависят от выбранной цепи и начального состояния.

Работает на: около 10^3 FLOPS приблизительно крошечная по современным меркам; в оригинале было несколько десятков масс. С: 1955 Исследования нелинейных задач Ферми, Пасты и Улама на раннем цифровом компьютере. [источник](https://doi.org/10.2172/4376203)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)[Частицы и задача N тел](https://simulation-hypothesis.com/ru/simulations/methods#m-particles)нижний уровень: Правила

### Численные эксперименты с солитонами

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

Вопрос, на который отвечает: Почему некоторые нелинейные волны проходят друг сквозь друга без изменений?

Не учитывает: Она показывает одно семейство уравнений, а не общее поведение нелинейных волн.

Работает на: около 10^4 FLOPS приблизительно одномерная сетка, сегодня тривиально. С: 1965 Взаимодействие солитонов в бесстолкновительной плазме и возвращение начальных состояний, Забуски и Крускал. [источник](https://doi.org/10.1103/physrevlett.15.240)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)[Непрерывные поля](https://simulation-hypothesis.com/ru/simulations/methods#m-continuum)нижний уровень: Правила

### Отрисовка фрактальных множеств

Простую итерируемую формулу проверяют в каждой точке комплексной плоскости: уходит ли она в бесконечность; так вычерчивают границу множества устойчивых точек.

Вопрос, на который отвечает: Какова форма множества, на котором простая итерация остаётся ограниченной?

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

Работает на: около 10^9 FLOPS приблизительно глубокое увеличение требует итераций повышенной точности в миллионах точек. С: 1980 Фрактальные аспекты итерации z → λz(1−z) Мандельброта, первые компьютерные изображения множества Мандельброта. [источник](https://doi.org/10.1111/j.1749-6632.1980.tb29690.x)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)нижний уровень: Правила

### Самоорганизованная критичность песчаной кучи

Песчинки падают на сетку и осыпаются, когда склон становится слишком крутым. Без всякой настройки получаются лавины всех размеров. Так моделируют, как системы приходят в критическое состояние.

Вопрос, на который отвечает: Почему лавины любого размера возникают без какой-либо настройки?

Не учитывает: Одинакова ли масштабная зависимость у настоящих систем, оспаривается.

Работает на: около 10^9 FLOPS приблизительно долгие расчёты на больших сетках, чтобы увидеть масштабирование. С: 1987 Самоорганизованная критичность Бака, Танга и Визенфельда: объяснение шума 1/f. [источник](https://doi.org/10.1103/physrevlett.59.381)

[Клеточные автоматы](https://simulation-hypothesis.com/ru/simulations/methods#m-cellular-automata)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

### Вычисление нулей дзета-функции Римана

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

Вопрос, на который отвечает: Лежат ли все нетривиальные нули дзета-функции на одной прямой?

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

Работает на: около 10^18 FLOPS приблизительно десятилетия процессорного времени в самых больших поисках. С: 1953 Расчёты дзета-функции Римана, выполненные Тьюрингом. [источник](https://doi.org/10.1112/plms/s3-3.1.99)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

### Цифры числа π на компьютере

Ряды для числа π суммируют до огромного числа знаков точной арифметикой, проверяя и число, и машину.

Вопрос, на который отвечает: Похожи ли цифры числа π на случайные, и можно ли доверять машине в таком масштабе?

Не учитывает: Цифры не отвечают ни на какой открытый вопрос, а проверки ловят аппаратные ошибки, только если метод независим.

Работает на: около 10^17 FLOPS приблизительно месяцы на сервере для сотен триллионов знаков. С: 1950 Определение числа π и e с точностью более 2000 знаков на ENIAC, Reitwiesner (опубликовано в 1950 году, перепечатано в Pi: A Source Book). [источник](https://doi.org/10.1007/978-1-4757-3240-5%5F34)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

### Поиск гипотез с помощью ИИ

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

Вопрос, на который отвечает: Какую пока не замеченную связь между этими математическими величинами стоит доказать?

Не учитывает: Она лишь подсказывает закономерности и сама ничего не доказывает, а некоторые закономерности в данных могут быть артефактами того, как данные получены.

Работает на: около 10^15 FLOPS приблизительно дни на нескольких видеокартах на набор данных. С: 2021 Работа Дэвиса с коллегами о продвижении математики через направление человеческой интуиции с помощью ИИ. [источник](https://doi.org/10.1038/s41586-021-04086-x)

[Выученные эмуляторы](https://simulation-hypothesis.com/ru/simulations/methods#m-learned)нижний уровень: Правила

### Поиск алгоритмов и конструкций с помощью обучения

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

Вопрос, на который отвечает: Может ли программа найти более быстрый алгоритм или больший пример, чем нашли люди?

Не учитывает: Каждый результат — один новый пример, а поиск охватывает лишь те виды объектов, которые его создатели оформили как игру.

Работает на: около 10^17 FLOPS приблизительно от дней до недель на кластерах ускорителей. С: 2022 AlphaTensor Фавзи с коллегами, открывающий более быстрые алгоритмы умножения матриц обучением с подкреплением. [источник](https://doi.org/10.1038/s41586-022-05172-4)

[Выученные эмуляторы](https://simulation-hypothesis.com/ru/simulations/methods#m-learned)[Эволюционные](https://simulation-hypothesis.com/ru/simulations/methods#m-evolutionary)нижний уровень: Правила

## Доказательства, логика и безопасность

### Проверка моделей

Каждое достижимое состояние конечной системы, например протокола или проекта схемы, перечисляется компьютером, чтобы проверить, что свойство выполняется во всех.

Вопрос, на который отвечает: Есть ли достижимое состояние, в котором эта конструкция нарушает собственные правила?

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

Работает на: около 10^12 FLOPS приблизительно университетский кластер, полностью перебирающий большое, но ограниченное пространство состояний С: 1981 Введение проверки моделей Кларком и Эмерсоном

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Автоматический поиск доказательств теорем

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

Вопрос, на который отвечает: Существует ли допустимая цепочка логических шагов от аксиом к этому утверждению?

Не учитывает: Находит доказательства, которые не выбрал бы ни один человек, а иногда не находит никаких в пределах досягаемости.

Работает на: около 10^11 FLOPS приблизительно университетский кластер, ищущий от часов до дней С: 1956 Logic Theorist, ранняя программа автоматического поиска доказательств

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### SAT и решение ограничений

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

Вопрос, на который отвечает: Есть ли набор значений, который удовлетворяет всем этим ограничениям сразу?

Не учитывает: Некоторые задачи настолько трудны, что ни один решатель, каким бы хорошим он ни был, не успевает их закончить.

Работает на: около 10^11 FLOPS приблизительно рабочая станция или кластер, в зависимости от размера задачи С: 1962 процедура Дэвиса и Патнэма для поиска по выполнимости

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### Моделирование криптографических атак

Схему шифрования или обмена ключами миллионы раз атакуют в симуляции: грубой силой, статистическим смещением или смоделированной слабостью. Так измеряют, сколько усилий на самом деле нужно, чтобы её взломать.

Вопрос, на который отвечает: Сколько операций на самом деле нужно, чтобы это взломать, и остаётся ли это число безопасно огромным?

Не учитывает: Проверяет только те атаки, которые аналитик додумался смоделировать, а не ту, которую никто ещё не нашёл.

Работает на: около 10^14 FLOPS приблизительно распределённый кластер из многих машин, запускающий испытания атак С: 1976 к 1976 году: вычислительный анализ стойкости шифров и обмена ключами

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Симуляция утечки по побочным каналам

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

Вопрос, на который отвечает: Какая часть секретного ключа утекает через физическое поведение устройства, а не через математику?

Не учитывает: В лабораторных условиях сигналы чище, чем обычно даёт шумное настоящее устройство.

Работает на: около 10^10 FLOPS приблизительно рабочая станция, моделирующая энергопотребление или тайминг одного устройства С: 1996 Демонстрация Кохера атак по времени на криптографические реализации

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)нижний уровень: Правила

### Верификация протоколов безопасности

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

Вопрос, на который отвечает: Может ли какая-нибудь последовательность сообщений обмануть этот протокол, заставив его выдать секрет или принять поддельную личность?

Не учитывает: Проверяет протокол в том виде, как он задан, а не лазейки, на которые идёт настоящая реализация.

Работает на: около 10^11 FLOPS приблизительно рабочая станция или кластер, проверяющие пространство сообщений одного протокола С: 1989 модель Долева и Яо, основополагающая база для проверки протоколов

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Сетевые модели](https://simulation-hypothesis.com/ru/simulations/methods#m-network)нижний уровень: Правила

### Компьютерное доказательство полным перебором случаев

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

Вопрос, на который отвечает: Можно ли завершить доказательство, если машина проверит все случаи?

Не учитывает: Доверие переходит к программе, оборудованию и доводу о сведении случаев.

Работает на: около 10^9 FLOPS приблизительно около тысячи часов на мэйнфрейме для оригинала; сейчас намного меньше. С: 1977 Доказательство Аппеля и Хакена, что любая плоская карта раскрашивается в четыре цвета, с компьютерной проверкой приводимости. [источник](https://doi.org/10.1215/ijm/1256049011)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)нижний уровень: Правила

### Проверенные вычисления

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

Вопрос, на который отвечает: Можно ли доказать, что вычисленный ответ верен, а не только вероятно точен?

Не учитывает: Границы могут разрастаться на больших временах, поэтому доказательства ограничены короткими или хорошо ведущими себя задачами.

Работает на: около 10^9 FLOPS приблизительно интервальная арифметика умножает затраты на скромный коэффициент. С: 2002 Строгий решатель ОДУ Такера и 14-я проблема Смейла, доказывающие, что аттрактор Лоренца существует. [источник](https://doi.org/10.1007/s002080010018)

[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)нижний уровень: Правила

### Перечисление машин Тьюринга

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

Вопрос, на который отвечает: Как долго может работать крошечная программа, прежде чем остановится?

Не учитывает: Неразрешимость означает, что некоторые машины никогда не удастся классифицировать, сколько бы они ни работали.

Работает на: около 10^15 FLOPS приблизительно миллиарды машин, с доказательствами для тех, что не останавливаются. С: 1965 Компьютерные исследования задач о машинах Тьюринга, Lin и Rado. [источник](https://doi.org/10.1145/321264.321270)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Дифференциальные уравнения](https://simulation-hypothesis.com/ru/simulations/methods#m-equations)нижний уровень: Правила

### Статистическая проверка моделей

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

Вопрос, на который отвечает: Насколько вероятно, что случайная система нарушит правило безопасности?

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

Работает на: около 10^9 FLOPS приблизительно от тысяч до миллионов выборочных выполнений. С: 2002 Вероятностная проверка дискретно-событийных систем с помощью приёмочной выборки, Юнес и Симмонс. [источник](https://doi.org/10.1007/3-540-45657-0%5F17)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

### Фаззинг-тестирование

Программе подают огромное число случайных или изменённых входных данных, чтобы найти те, что приводят к сбою; по сути, это симуляция враждебного или небрежного мира.

Вопрос, на который отвечает: Какой ввод заставит эту программу сбоить?

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

Работает на: около 10^14 FLOPS приблизительно машино-годы процессорного времени для большой кодовой базы. С: 1990 Эмпирическое исследование надёжности утилит UNIX, Miller, Fredriksen и So. [источник](https://doi.org/10.1145/96267.96279)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)[Эволюционные](https://simulation-hypothesis.com/ru/simulations/methods#m-evolutionary)нижний уровень: Правила

### Символическое выполнение

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

Вопрос, на который отвечает: Какие входы запускают каждый путь этой программы и приводит ли какой-нибудь к ошибке?

Не учитывает: Число путей растёт экспоненциально с размером программы, поэтому крупные охватываются лишь частично.

Работает на: около 10^12 FLOPS приблизительно часов работы решателя на программу, с резким ростом при увеличении числа путей. С: 1976 Символическое выполнение и тестирование программ, King. [источник](https://doi.org/10.1145/360248.360252)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

### Абстрактная интерпретация

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

Вопрос, на который отвечает: Может ли эта программа когда-нибудь разделить на ноль или переполниться при каких-то входных данных?

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

Работает на: около 10^11 FLOPS приблизительно часов на рабочей станции для большой базы кода бортовой электроники. С: 1977 Абстрактная интерпретация Кусо и Кусо, единая решёточная модель статического анализа программ. [источник](https://doi.org/10.1145/512950.512973)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

### Ограниченная проверка моделей

Поведение конструкции на заданное число шагов записывают как логическую формулу и передают решателю выполнимости, чтобы найти любой короткий путь к ошибке.

Вопрос, на который отвечает: Может ли эта схема или программа достичь состояния ошибки за заданное число шагов?

Не учитывает: Она ничего не доказывает за пределами границы по шагам, пока отдельное рассуждение не покажет, что её достаточно.

Работает на: около 10^13 FLOPS приблизительно часов на сервере на один объект. С: 1999 Символическая проверка моделей без BDD Биере, Чиматти, Кларка и Чжу. [источник](https://doi.org/10.21236/ada360973)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

### Случайное тестирование по свойствам

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

Вопрос, на который отвечает: Соблюдает ли этот код собственную спецификацию на широком наборе входных данных?

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

Работает на: около 10^9 FLOPS приблизительно минуты на ноутбуке для тысяч случаев. С: 2000 QuickCheck Клаэссена и Хьюза, лёгкий инструмент случайного тестирования программ на Haskell. [источник](https://doi.org/10.1145/351240.351266)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Верификация нейронных сетей

Решатели ограничений доказывают, что для любых входных данных из области выход нейросети остаётся в границах, вместо проверки на выборках.

Вопрос, на который отвечает: Может ли небольшое изменение входных данных заставить сеть дать неверный ответ?

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

Работает на: около 10^13 FLOPS приблизительно от часов до суток на сервере для небольшой сети. С: 2017 Reluplex Katz и коллег, SMT-решатель для проверки глубоких нейронных сетей. [источник](https://doi.org/10.1007/978-3-319-63387-9%5F5)

[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Из первых принципов](https://simulation-hypothesis.com/ru/simulations/methods#m-first-principles)нижний уровень: Правила

## Системы и машины

### Симуляция компьютерной архитектуры

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

Вопрос, на который отвечает: Как быстро эта конструкция процессора выполняла бы настоящие программы, пока ещё не вырезан ни один кремниевый кристалл?

Не учитывает: Упрощает настоящий чип настолько, что готовый кремний всегда немного отличается от модели.

Работает на: около 10^11 FLOPS приблизительно университетский кластер, прогоняющий через модель эталонные программы С: 1990 к 1990 году: потактно точные симуляторы процессоров для исследований архитектуры

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Симуляция распределённых систем и консенсуса

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

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

Не учитывает: Вводятся те сбои, которые предвидел разработчик, а не те, что неожиданно возникают в работе.

Работает на: около 10^10 FLOPS приблизительно кластер, моделирующий сотни виртуальных узлов С: 1978 Ранняя работа Лэмпорта о порядке и сбоях в распределённых системах

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Сетевые модели](https://simulation-hypothesis.com/ru/simulations/methods#m-network)нижний уровень: Правила

### Моделирование систем хранения

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

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

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

Работает на: около 10^10 FLOPS приблизительно рабочая станция или небольшой кластер, моделирующие массив хранения данных С: 1988 к 1988 году: симуляционные модели надёжности дисковых массивов

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

### Симуляция планировщика операционной системы

Поток вычислительных задач моделируется так, что они поступают и спорят за процессор; его гоняют при разных правилах планирования, чтобы увидеть, какое из них самое справедливое или быстрое.

Вопрос, на который отвечает: Какой порядок очереди задач позволяет сделать больше всего работы или честнее ко всем задачам?

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

Работает на: около 10^9 FLOPS приблизительно работает на ноутбуке или рабочей станции за секунды или минуты С: 1968 к 1968 году: симуляционные исследования правил планирования процессора

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)нижний уровень: Правила

### Поиск оптимизаций компиляторов и программ

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

Вопрос, на который отвечает: Какой из равнозначных способов записать этот небольшой кусок кода на самом деле работает быстрее всех?

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

Работает на: около 10^10 FLOPS приблизительно кластер, который перебирает большое пространство вариантов кода С: 2006 к 2006 году: поиск супероптимизации по коротким последовательностям инструкций

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Эмпирическая проверка производительности алгоритмов

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

Вопрос, на который отвечает: Как на самом деле растёт время работы этого алгоритма на тех входных данных, которые он будет получать?

Не учитывает: Худший случай, которого нет среди тестовых входных данных, остаётся незамеченным, пока не наступит.

Работает на: около 10^9 FLOPS приблизительно работает на рабочей станции на множестве сгенерированных тестовых входов С: 1970 к 1970 году: систематическая экспериментальная проверка времени работы алгоритмов

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

### Выполнение программ языковой моделью

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

Вопрос, на который отвечает: Может ли языковая модель эмулировать выполнение кода?

Не учитывает: Правильность результата не гарантируется, а длинные программы дают сбои.

Работает на: около 10^14 FLOPS приблизительно Вывод на каждый запрос С: 2021 Show your work: scratchpads for intermediate computation with language models (2021) [источник](https://arxiv.org/abs/2112.00114)

[Выученные эмуляторы](https://simulation-hypothesis.com/ru/simulations/methods#m-learned)нижний уровень: Правила

### Симуляция консенсуса в блокчейне

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

Вопрос, на который отвечает: Насколько безопасен и быстр блокчейн при сетевых задержках и атаках?

Не учитывает: Настоящее поведение узлов и топологии сетей измерены лишь частично.

Работает на: около 10^8 FLOPS приблизительно событийные прогоны с тысячами узлов. С: 2016 Анализ безопасности и производительности блокчейнов с доказательством работы на симуляторе Жерве с коллегами. [источник](https://doi.org/10.1145/2976749.2978341)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Агентные](https://simulation-hypothesis.com/ru/simulations/methods#m-agent-based)[Сетевые модели](https://simulation-hypothesis.com/ru/simulations/methods#m-network)нижний уровень: Популяции

### Параллельная дискретно-событийная симуляция

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

Вопрос, на который отвечает: Как быстро запускать на многих машинах огромную событийную симуляцию, например сети или поля боя?

Не учитывает: Откаты могут идти каскадом, а ускорение сильно зависит от того, насколько тесно связаны события.

Работает на: около 10^14 FLOPS приблизительно часов на суперкомпьютере для миллиардов событий. С: 1985 Виртуальное время Джефферсона, механизм Time Warp для оптимистичной синхронизации. [источник](https://doi.org/10.1145/3916.3988)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)нижний уровень: Правила

### Симуляция архитектуры графического процессора

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

Вопрос, на который отвечает: Как изменение конструкции повлияет на скорость параллельных программ на графическом чипе?

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

Работает на: около 10^12 FLOPS приблизительно от часов до суток времени хоста на секунду симулируемого выполнения. С: 2009 Анализ Баходы с коллегами нагрузок CUDA на подробном симуляторе графического процессора. [источник](https://doi.org/10.1109/ispass.2009.4919648)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)нижний уровень: Правила

### Симуляция систем с ускорением на FPGA

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

Вопрос, на который отвечает: Как этот процессор и его кластер поведут себя при работе настоящих программ, пока они не изготовлены?

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

Работает на: около 10^15 FLOPS приблизительно дни на облаке из сотен перенастраиваемых схем. С: 2018 FireSim Karandikar и коллег: точная по тактам масштабная симуляция систем на FPGA в публичном облаке. [источник](https://doi.org/10.1109/isca.2018.00014)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Реальное время](https://simulation-hypothesis.com/ru/simulations/methods#m-real-time)нижний уровень: Правила

### Симуляция всей системы

Целый компьютер с процессорами, памятью, дисками и сетевыми картами моделируется достаточно хорошо, чтобы загрузить немодифицированную операционную систему и запустить её программы.

Вопрос, на который отвечает: Как ведёт себя настоящее программное обеспечение на машине, которой ещё нет или которую можно ставить на паузу и проигрывать заново?

Не учитывает: Временные характеристики приближены ради скорости, поэтому нельзя получить точную производительность, только функциональное поведение.

Работает на: около 10^11 FLOPS приблизительно почти в реальном времени на сервере на одну смоделированную машину. С: 2002 Simics, платформа симуляции целых систем, Magnusson и коллеги. [источник](https://doi.org/10.1109/2.982916)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Правила и состояния](https://simulation-hypothesis.com/ru/simulations/methods#m-rules)[Реальное время](https://simulation-hypothesis.com/ru/simulations/methods#m-real-time)нижний уровень: Правила

### Лёгкая эмуляция сетей

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

Вопрос, на который отвечает: Будет ли эта программа управления сетью работать на всей топологии до развёртывания?

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

Работает на: около 10^10 FLOPS приблизительно в реальном времени на одной рабочей станции. С: 2010 «A network in a laptop» Lantz, Heller и McKeown: быстрое прототипирование программно-определяемых сетей. [источник](https://doi.org/10.1145/1868447.1868466)

[Дискретные события](https://simulation-hypothesis.com/ru/simulations/methods#m-discrete-event)[Сетевые модели](https://simulation-hypothesis.com/ru/simulations/methods#m-network)[Реальное время](https://simulation-hypothesis.com/ru/simulations/methods#m-real-time)нижний уровень: Правила

### Имитация отжига

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

Вопрос, на который отвечает: Какая раскладка или расписание близки к лучшим среди астрономического числа возможностей?

Не учитывает: Она не гарантирует лучший ответ, а результаты зависят от графика охлаждения.

Работает на: около 10^12 FLOPS приблизительно часов на рабочей станции для размещения элементов чипа. С: 1983 Оптимизация имитацией отжига, Kirkpatrick, Gelatt и Vecchi. [источник](https://doi.org/10.1126/science.220.4598.671)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

### Приближённые байесовские вычисления

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

Вопрос, на который отвечает: Какие настройки сложной модели могли бы дать наблюдаемые нами данные?

Не учитывает: Результат зависит от того, какие сводки данных используются и насколько близким должно быть совпадение.

Работает на: около 10^13 FLOPS приблизительно миллионы прогонов симулятора на кластере. С: 1997 Вывод времён коалесценции из данных о последовательностях ДНК с помощью симуляции, Таваре с коллегами. [источник](https://doi.org/10.1093/genetics/145.2.505)

[Монте-Карло](https://simulation-hypothesis.com/ru/simulations/methods#m-monte-carlo)[Стохастические процессы](https://simulation-hypothesis.com/ru/simulations/methods#m-stochastic)нижний уровень: Правила

[◂ Сознания, мозги и искусственные миры](https://simulation-hypothesis.com/ru/simulations/minds-computation)[Сознания как симуляторы ▸](https://simulation-hypothesis.com/ru/simulations/mind-simulations)