Случай известного вычислимого мира

Рассмотрим сначала простейший случай среды, полностью описывающейся известной машиной Тьюринга (алгоритмом или программой для универсальной машины Тьюринга) q’, входом которой на момент времени k являются действия агента y_{1},...,y_{k}, а выходом – значения o_{k} и r_{k}. Сам агент также управляется некоторой программой p’, входом которой являются o_{1}r_{1},...o_{k-1}r_{k-1}, т.е. x_{1},...x_{k-1}, а выходом – значение y_{k}.

Для краткости последовательности вида y_{m}...y_{n} будем обозначать ymy_{m:n}, а при m=1 будем писать y_{\leq n} или y_{\leq n+1}. Для обозначения множества последовательностей, составленных из объектов множества Y, будет использовать традиционное обозначение Y*. Тогда программы q’ и p’ задают соответствующие отображения q′ :Y* → X и p′ : X * →Y , причем x_{k}=q'(y_{\leq k}) и y_{k}=p'(x_{\leq k}). Также будем писать o_{k}=q_{o}'(y_{\leq k}) и r_{k}=q_{r}'(y_{\leq k}) для соответствующих компонентов x_{k}. Здесь полагается, что на каждом такте времени программы запускаются поочередно: сначала запускается p’, а потом – q’, причем в начальный момент времени строка x_{\lt 1} является пустой. Принципиальной асимметрии между средой и агентом здесь нет (за исключением начального момента времени), поскольку запуски p’ и q’ постоянно чередуются, и отнесение двух запусков к одному такту условно. Здесь, естественно, не принимается в расчет время вычисления p’ и q’, но в остальном такая постановка выглядит достаточно естественной. Нужно подчеркнуть, что никакого «реального времени» здесь в принципе нет: эти программы работают не постоянно, а вызываются на каждом такте заново. Тогда текущий результат взаимодействия агента с миром может быть вычислен в цикле:

formula_35

Чтобы избавиться от асимметрии (вернее, от полутактов), можно было бы x_{t} считать как q'(y_{\lt t}). С формальной точки зрения это приведет к постановке другой задачи. Так, исходная постановка с x_{t}=q'(y_{\leq t}) подходит для описания игры в шахматы, но не в игру «камень-ножницы-бумага», тогда как вариант с x_{t}=q'(y_{\lt t}) – наоборот. Однако поскольку оба эти варианта не учитывают необходимость вычисления q’ в масштабе реального времени, с введением которой различия между ними будут устранены, на данном этапе практически без разницы, какой из них использовать за исключением искусственных случаев типа упомянутых игр, правила которых определяют конкретную организацию последовательности «ходов» агента и среды (стоит также отметить некорректность вариантаy_{t}=p'(x_{\leq t}), x_{t}=q'(y_{\leq t}). Естественно, при реальной игре в «камень-ножницы-бумагу» абсолютной одновременности ходов нет, а есть ли она на уровне элементарных действий, практически не важно (здесь можно вспомнить о реально работающем роботе, который выигрывает в эту игру у человека за счет распознавания выбора человека до обозначения собственного выбора). Также и при реальной игре в шахматы очередность ходов может быть «физически» легко нарушена.

Для удобства также введем программы p и q, такие что x_{1:k}=q(y_{\leq k}) и y_{1:k}=p(x_{\lt k}), то есть p – программа, которая не просто выбирает текущие действия, а возвращает всю их историю. Эквивалентные программы p и p’ (q и q’) могут быть легко получены друг из друга, поэтому их введение здесь – не более чем вопрос удобства. Поскольку формируемые строки из x и y зависят от обеих программ p и q в силу рекурсивности вызовов q(y_{\leq k})=q(p(x_{\lt k}))=q(p(q(y_{\lt k}))), конкретный элемент истории, сформированной p и q, будем обозначать через, например,  r_{t}^{pq},y_{1:k}^{pq} и т.д.

Поскольку p и q детерминированы, можно для них посчитать будущий (после текущего момента k до некоторого момента m) суммарный выигрыш, который получит агент:

formula_36

Теперь мы можем корректно поставить задачу определения лучшей политики p* и лучшего текущего действия:

formula_37

Решение задачи поиска оптимальной стратегии p* под конкретную среду q может быть выполнено априорно по формуле (2.1.2), хотя построение такого оптимального интеллектуального агента может быть весьма нетривиальным, так как непосредственно применить данную формулу на практике обычно невозможно из соображений вычислительной сложности.

Кажется, что программы p* для разных сред должны быть принципиально различными. В этой связи весьма примечательно, что существует универсальная программа выбора оптимальных действий по модели среды q. Собственно, уравнение (2.1.2) и задает такую программу. Но можно предложить и другую универсальную программу, которая выбирает оптимальные действия непосредственно, а не через поиск частной оптимальной программы. Такая программа задается следующим выражением:

formula_38

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