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

Question

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

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

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

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

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

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

Answer 1

Райан, мой ответ однозначно "ДА".

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

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

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

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

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

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

Объяснение:

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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