Состояние и время, пересекающие логику и ход программы?

Question

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

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

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

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

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

Может быть, для моделирования, но это заняло бы тонну памяти.

Answer 1

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

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

Так что да, это поддается, но не без ограничений.

Answer 2

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

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

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

for (int i=0; i < 100; i++)
    some_function();

Тогда число возможных состояний (количество ветвей внутри some_function) ^ 100

Answer 3

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

Answer 4

Райан, ответ окончательно ДА.

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

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

Точный объем памяти, необходимый для хеширования, будет:

(2)*(program state size)*(number of initial states)

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

Для операционной системы «размер состояния программы» равен 2 ^ (общее количество гигабайт памяти на всех системных устройствах). Очевидно, что такая большая программа общего назначения потребует непрактичного объема памяти для хеширования, и в любом случае она не будет полезна, поскольку система является самоссылающейся / неснижаемо сложной (т. Е. Следующий пользовательский ввод зависит от предыдущего вывода системы).

Пояснение:

Это очень полезно, потому что если вы индексируете каждое возможное начальное состояние и связываете его с завершающим состоянием, вы фактически сведете время выполнения ЛЮБОЙ ПРОГРАММЫ к нулю! Любой под нулем я подразумеваю очень быстрое время работы O (1) - время, необходимое для поиска состояния завершения (если оно завершается).

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

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

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

   для (int i = 0; true; i ++); // я достигну максимального значения, вернемся к нулю, после чего он вернется в исходное состояние

Итак, в принципе, ваш индекс можно описать так:

• Для каждого начального состояния существует ровно одно или ноль конечных состояний.

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

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

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

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

Это доказывает, что любая программа может быть представлена ​​хеш-таблицей.Любая программа может быть представлена ​​картой перехода между начальным и конечным состояниями. Все программы можно упростить до одной большой функции с огромным объемом памяти!

Answer 5

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

Answer 6

Это делается на функциональном уровне; это техника под названием памятка .