Машина Гёделя

Машина Гёделя — это гипотетическая компьютерная программа, способная к самосовершенствованию и оптимальному решению задач. Она использует рекурсивный протокол самоускорения, перезаписывая собственный код, когда может доказать, что новый код обеспечивает лучшую стратегию^[1]^[2]. Концепция машины Гёделя была предложена Юргеном Шмидхубером (впервые описана в 2003 году^[3]), а своё название получила в честь математика Курта Гёделя, чьи математические идеи её вдохновили^[4].

Машина Гёделя часто обсуждается в контексте метаобучения («обучения учиться»). Среди её применений — автоматизация принятия решений и перенос знаний между множеством родственных задач, что может привести к созданию более универсальных и устойчивых архитектур машинного обучения^[5]. Несмотря на теоретическую осуществимость, полноценной реализации машины Гёделя на практике пока не создано^[6].

Машина Гёделя часто сравнивается со спецификацией AIXItl Маркуса Хуттера, представляющей другую формальную модель искусственного общего интеллекта. Шмидхубер отмечает, что машина Гёделя может начинать с реализации AIXItl в качестве начального подпроцесса, а затем автоматически модифицировать себя после нахождения доказательств преимущества иного поискового алгоритма^[7].

Традиционные задачи, решаемые компьютерами, обычно требуют ввода и предоставления результата; такие компьютеры работают с «жёстко зашитыми» алгоритмами^[7]. Это не учитывает изменение естественной среды, что и являлось одним из препятствий, которые должна преодолеть машина Гёделя.

Тем не менее, машина Гёделя имеет и собственные ограничения. Любая формальная система, включающая арифметику, либо противоречива, либо допускает утверждения, которые нельзя доказать в данной системе, но можно доказать в других^[3] Следовательно, даже машина Гёделя с неограниченными вычислительными ресурсами вынуждена игнорировать такие самосовершенствования, эффективность которых не может доказать.

Во время работы машины Гёделя есть три ключевые переменные, имеющие особое значение.^[3].

В некоторый момент времени $t$ переменная ${\text{time}}$ содержит двоичное представление $t$ . Это значение постоянно увеличивается с прогрессом исполнения.
Любые входные данные, поступающие в машину Гёделя из внешней среды, сохраняются в переменной $x$ , причём $x$ может меняться для разных значений ${\text{time}}$ .
Выходные данные машины Гёделя записываются в переменные $y$ , где $y(t)$ — битовая строка вывода в момент времени $t$ .

В каждый момент времени $t$ , где $(1\leq t\leq T)$ , цель — максимизировать успех (или полезность) в будущем. Типичная функция полезности описывается формулой $u(s,\mathrm {Env} ):S\times E\to \mathbb {R}$ :

u(s,\mathrm {Env} )=E_{\mu }{\Bigg [}\sum _{\tau ={\text{time}}}^{T}r(\tau )\mid s,\mathrm {Env} {\Bigg ]}

где $r(t)$ — входная величина вознаграждения (закодирована в $s(t)$ ) в момент $t$ , $E_{\mu }[\cdot \mid \cdot ]$ обозначает оператор условного матожидания относительно (возможно, неизвестного) распределения $\mu$ из множества $M$ возможных распределений (отражающих всю доступную информацию о вероятностных реакциях среды), а ${\text{time}}=\operatorname {time} (s)$ — функция состояния $s$ , идентифицирующая текущий цикл. При этом рассматривается возможность увеличения ожидаемой продолжительности жизни через осмысленные действия.

Суть шести приведённых ниже инструкций заключается в том, что теорема с ошибкой не может быть внедрена в доказательство, что делает проверку тривиальной^[3].

get-axiom (n)

Добавляет n-ый аксиому в текущую последовательность теорем. Начальный набор аксиом включает:

Аксиомы аппаратного обеспечения формально описывают возможные переходы между состояниями компонентов машины.
Аксиомы вознаграждений определяют вычислительную стоимость аппаратных инструкций и физическую стоимость выходных действий. Связанные аксиомы задают ожидаемую продолжительность работы машины Гёделя в виде скалярных значений для всех наград и затрат.
Аксиомы среды ограничивают возможные поступления новых входных данных $x$ на основании предыдущих входных и выходных данных.
Аксиомы неопределённости/манипуляции строками — стандартные аксиомы арифметики, исчисления, теории вероятностей и работы со строками, позволяющие проводить доказательства, связанные со значениями переменных в будущем состоянии машины Гёделя.
Аксиомы начального состояния содержат информацию о восстановлении частичного или полного начального состояния.
Аксиомы полезности формализуют общую цель в виде функции полезности u.

apply-rule(k, m, n)

Берёт индекс k некоторого правила вывода (например, modus tollens, modus ponens), и пытается применить его к двум ранее доказанным теоремам m и n. Полученная теорема добавляется в доказательство.

delete-theorem(m)

Удаляет теорему с индексом m из текущего доказательства. Это полезно для экономии памяти, устраняя избыточные и ненужные теоремы. Удалённые теоремы больше недоступны функции apply-rule.

set-switchprog(m, n)

Заменяет switchprog S^{p}_{m: n}, если это непустая подстрока S^{p}.

check()

Проверяет, достигнута ли цель поиска доказательств. Целевая теорема утверждает, что, исходя из текущей аксиоматизированной функции полезности u (см. выше), полезность перехода от программы p к текущему switchprog превышает полезность продолжения исполнения p (то есть поиска прочих switchprog).^[3] Это реализуется, например, с помощью проверочной функции check() для машины Гёделя:

D_{KA}={\frac {d_{\text{pore}}}{3}}u={\frac {d_{\text{pore}}}{3}}{\sqrt {\frac {8\kappa NT}{\pi M_{A}}}}

state2theorem(m, n)

Получает два аргумента, m и n, и пытается преобразовать содержимое $S_{m:n}$ в теорему.

Ограниченная по времени оптимизация NP-трудной задачи

В начальные входные данные машине Гёделя поступает описание связного графа с большим числом вершин, соединённых рёбрами разной длины. За установленное время T требуется найти циклический маршрут, проходящий через все узлы. Единственное вознаграждение с ненулевым значением будет получено в момент T, оно равно 1, делённому на длину наилучшего найденного маршрута (0, если маршрут не найден). Других входных данных нет. Таким образом, максимизация ожидаемой награды приводит к поиску минимального по длине пути при заданном времени и исходных условиях.^[3]

Быстрое доказательство теорем

Как можно скорее доказать или опровергнуть утверждение о том, что любое чётное целое число больше 2 представимо в виде суммы двух простых чисел (Гипотеза Гольдбаха). Награда составляет 1/t, где t — время, затраченное на нахождение и проверку первого доказательства.^[8].

Максимизация ожидаемой награды с ограниченными ресурсами

Когнитивный робот, расходующий минимум 1 литр топлива в час, взаимодействует с частично неизвестной средой, пытаясь время от времени находить спрятанные и конечные запасы бензина для дозаправки бака. Он получает награду пропорционально продолжительности существования и погибает либо не позднее чем через 100лет, либо сразу, как только бак опустеет или, например, упадёт с обрыва. Вероятностные реакции среды изначально неизвестны, однако предполагается, что экстремально сложные для вычисления сценарии маловероятны. Это позволяет реализовать вычислимую стратегию, близкую к оптимальной. Максимизация ожидаемой награды влечёт за собой также рост ожидаемой продолжительности жизни^[3].

↑ Mahmud, M. M. Hassan. Universal Transfer Learning. — 2008. — P. 16–18. — ISBN 9780549909880.
↑ Anderson, Michael L.; Oates, Tim (весна 2007). “A review of recent research in metareasoning and metalearning”. AI Magazine [англ.]. 28 (1): 7. Архивировано из оригинала 2017-09-07. Дата обращения 2024-06-20. Используется устаревший параметр |url-status= (справка); Проверьте дату в |date= (справка на английском)
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Schmidhuber, Jürgen. Gödel Machines: Self-Referential ¨ Universal Problem Solvers Making Provably Optimal Self-Improvements : [англ.]. — декабрь 2006.
↑ Gödel machine (англ.). Дата обращения: 20 июня 2024. Архивировано 3 декабря 2012 года.
↑ Schaul, Tom; Schmidhuber, Juergen (2010). “Metalearning”. Scholarpedia [англ.]. 5 (6): 4650. DOI:10.4249/scholarpedia.4650. Дата обращения 2024-06-20.
↑ Steunebrink, Bas R. A Family of Gödel Machine Implementations / Bas R. Steunebrink, Jürgen Schmidhuber. — 2011. — Vol. 6830. — P. 275–280. — ISBN 978-3-642-22886-5. — doi:10.1007/978-3-642-22887-2_29.
↑ ¹ ² Schmidhuber, Jürgen (5 марта 2009). “Ultimate Cognition à la Gödel” (PDF). Cognitive Computation [англ.]. 1 (2): 177—193. DOI:10.1007/s12559-009-9014-y. Дата обращения 2024-06-20.
↑ Schmidhuber, Jürgen (5 марта 2009). “Ultimate Cognition à la Gödel”. Cognitive Computation [англ.]. 1 (2): 177—193. DOI:10.1007/s12559-009-9014-y. Дата обращения 2024-06-20. |access-date= требует |url= (справка)

Mahmud, M. M. Hassan. Universal Transfer Learning. — 2008. — P. 16–18. — ISBN 9780549909880.
Anderson, Michael L.; Oates, Tim (весна 2007). “A review of recent research in metareasoning and metalearning”. AI Magazine [англ.]. 28 (1): 7. Архивировано из оригинала 2017-09-07. Дата обращения 2024-06-20. Используется устаревший параметр |url-status= (справка); Проверьте дату в |date= (справка на английском)
Schaul, Tom; Schmidhuber, Juergen (2010). “Metalearning”. Scholarpedia [англ.]. 5 (6): 4650. DOI:10.4249/scholarpedia.4650. Дата обращения 2024-06-20.
Steunebrink, Bas R. A Family of Gödel Machine Implementations / Bas R. Steunebrink, Jürgen Schmidhuber. — 2011. — Vol. 6830. — P. 275–280. — ISBN 978-3-642-22886-5. — doi:10.1007/978-3-642-22887-2_29.
Schmidhuber, Jürgen. Gödel Machines: Self-Referential ¨ Universal Problem Solvers Making Provably Optimal Self-Improvements : [англ.]. — декабрь 2006.
Schmidhuber, Jürgen (5 марта 2009). “Ultimate Cognition à la Gödel” (PDF). Cognitive Computation [англ.]. 1 (2): 177—193. DOI:10.1007/s12559-009-9014-y. Дата обращения 2024-06-20.

Страница о машине Гёделя

[1] Mahmud, M. M. Hassan. Universal Transfer Learning. — 2008. — P. 16–18. — ISBN 9780549909880.

[2] Anderson, Michael L.; Oates, Tim (весна 2007). “A review of recent research in metareasoning and metalearning”. AI Magazine [англ.]. 28 (1): 7. Архивировано из оригинала 2017-09-07. Дата обращения 2024-06-20. Используется устаревший параметр |url-status= (справка); Проверьте дату в |date= (справка на английском)

[Gödel_Machines.-3] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Schmidhuber, Jürgen. Gödel Machines: Self-Referential ¨ Universal Problem Solvers Making Provably Optimal Self-Improvements : [англ.]. — декабрь 2006.

[4] Gödel machine (англ.). Дата обращения: 20 июня 2024. Архивировано 3 декабря 2012 года.

[5] Schaul, Tom; Schmidhuber, Juergen (2010). “Metalearning”. Scholarpedia [англ.]. 5 (6): 4650. DOI:10.4249/scholarpedia.4650. Дата обращения 2024-06-20.

[6] Steunebrink, Bas R. A Family of Gödel Machine Implementations / Bas R. Steunebrink, Jürgen Schmidhuber. — 2011. — Vol. 6830. — P. 275–280. — ISBN 978-3-642-22886-5. — doi:10.1007/978-3-642-22887-2_29.

[Sin_nombre-pFF0-1-7] ¹ ² Schmidhuber, Jürgen (5 марта 2009). “Ultimate Cognition à la Gödel” (PDF). Cognitive Computation [англ.]. 1 (2): 177—193. DOI:10.1007/s12559-009-9014-y. Дата обращения 2024-06-20.

[8] Schmidhuber, Jürgen (5 марта 2009). “Ultimate Cognition à la Gödel”. Cognitive Computation [англ.]. 1 (2): 177—193. DOI:10.1007/s12559-009-9014-y. Дата обращения 2024-06-20. |access-date= требует |url= (справка)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Машина Гёделя

Ограничения

Важные переменные

Инструкции, используемые при доказательстве

get-axiom (n)

apply-rule(k, m, n)

delete-theorem(m)

set-switchprog(m, n)

check()

state2theorem(m, n)

Примеры применения

Ограниченная по времени оптимизация NP-трудной задачи

Быстрое доказательство теорем

Максимизация ожидаемой награды с ограниченными ресурсами

Примечания

Литература

Ссылки

Категории