повествование. К некоторым из них будет возможность вернуться в главе 12.
32
Программа p генерирует полное описание строки x, если p, запущенная на (некоторой) универсальной машине Тьюринга U, выдает x; это можно записать как U(p) = x. (Здесь строка x представляет любой возможный мир.) Тогда колмогоровская сложность x равна K(x) = minp {l(p): U(p) = x}, где l(p) это длина p в битах. Соломоновская вероятность x определяется как
, где сумма задана над всеми («минимальными», то есть не обязательно останавливающимися) программами p, для которых U выдает строку, начинающуюся с x; см.: [Hutter 2005].33
Байесово обусловливание с учетом свидетельства Е дает (вероятность утверждения [например, Е] есть сумма вероятностей возможных миров, в которых это утверждение истинно.)
34
Или случайным образом выбирает одно из возможных действий с максимальной ожидаемой полезностью, если их несколько.
35
Более сжато ожидаемая полезность действия может быть записана как
, где сумма берется по всем возможным мирам.36
См., например: [Howson, Urbach 1993; Bernardo, Smith 1994; Russell, Norvig 2010].
37
См.: [Wainwright, Jordan 2008]. У байесовских сетей бесчисленное количество областей применения; см., например: [Pourret et al. 2008].
38
Возможно, некоторые читатели, сочтя это направление не слишком серьезным, зададут вопрос: зачем уделять столь пристальное внимание компьютерным играм? Дело в том, что игровые интеллектуальные системы, пожалуй, дают самое наглядное представление о сравнительных возможностях человека и машины.
39
См.: [Samuel 1959; Schaeffer 1997, ch. 6].
40
См.: [Schaeffer et al. 2007].
41
См.: [Berliner 1980 a; Berliner 1980 b].
42
См.: [Tesauro 1995].
43
В частности, такие программы по игре в нарды, как GNU [Silver 2006] и Snowie [Gammoned.net, 2012].
44
Процессом создания космического флота и битвами руководил сам Дуглас Ленат, написавший по этому поводу: «Итак, победа стала заслугой и Лената, и Eurisco – в пропорции 60: 40. Основной момент тем не менее состоит в том, что в одиночку ни я, ни программа никогда не справились бы» [Lenat 1983, p. 80].
45
См.: [Lenat 1982; Lenat 1983].
46
См.: [Cirasella, Kopec 2006].
47
См.: [Kasparov 1996, p. 55].
48
См.: [Newborn 2011].
49
См.: [Keim et al. 1999].
50
См.: [Armstrong 2012].
51
См.: [Sheppard 2002].
52
См.: [Wikipedia, 2012 a].
53
См.: [Markoff 2011].
54
См.: [Rubin, Watson 2011].
55
См.: [Elyasaf et al. 2011].
56
См.: [KGS, 2012].
57
См.: [Newell et al. 1958, p. 320].
58
См.: [Vardi 2012].
59
Ирвинг Гуд предполагал в 1976 году:
Появление