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

редактировать

A Машина Гёделя - это гипотетическая самоулучшающаяся компьютерная программа, которая решает проблемы оптимальным образом. Он использует рекурсивный протокол самоулучшения, в котором он переписывает свой собственный код, когда может доказать, что новый код обеспечивает лучшую стратегию. Машина была изобретена Юргеном Шмидхубером (впервые предложена в 2003 году), но названа в честь Курта Гёделя, вдохновителя математических теорий.

Часто обсуждается машина Гёделя. при решении вопросов метаобучения, также известного как «обучение, чтобы учиться». Приложения включают автоматизацию проектных решений, принимаемых человеком, и передачу знаний между множеством связанных задач и могут привести к разработке более надежных и общих архитектур обучения. Хотя теоретически это возможно, полная реализация не была создана.

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

Содержание

1 Ограничения
2 интересующие переменные
3 инструкции, используемые методами доказательства
- 3.1 get-axiom (n)
- 3.2 apply-rule (k, m, n)
- 3.3 delete-Theorem (m)
- 3.4 set-switchprog (m, n)
- 3.5 check ()
- 3.6 state2theorem (m, n)
4 Примеры приложений
- 4.1 Ограниченная по времени NP-жесткая оптимизация
- 4.2 Быстрая теорема доказательство
- 4.3 Максимизация ожидаемого вознаграждения с ограниченными ресурсами
5 См. также
6 Ссылки
7 Внешние ссылки

Ограничения

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

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

Интересующие переменные

Есть три переменные, которые особенно полезны во время выполнения Машина Гёделя.

Через некоторое время $t {\ displaystyle t}$ $t$ переменная $time {\ displaystyle {\ text {time}}}$ ${\ displaystyle {\ text {time}}}$ будет иметь двоичный эквивалент $t {\ displaystyle t}$ $t$ . Это значение постоянно увеличивается на протяжении всего времени работы машины.

Любой ввод, предназначенный для машины Гёделя из естественной среды, сохраняется в переменной $x {\ displaystyle x}$ $x$ . Вероятно, что $x {\ displaystyle x}$ $x$ будет содержать разные значения для разных значений переменной $time {\ displaystyle {\ text {time}}}$ ${\ displaystyle {\ text {time}}}$ .

Выходные данные машины Гёделя хранятся в переменной $y {\ displaystyle y}$ $y$ , где $y (t) {\ displaystyle y (t)}$ $y (t)$ будет выходным битовая строка в какой-то момент $t {\ displaystyle t}$ $t$ .

В любой момент $t {\ displaystyle t}$ $t$ , где $(1 ≤ t ≤ T) { \ displaystyle (1 \ leq t \ leq T)}$ ${ \ displaystyle (1 \ leq t \ leq T)}$ , цель - максимизировать будущий успех или полезность. Типичная функция полезности следует шаблону $u (s, E nv): S × E → R {\ displaystyle u (s, \ mathrm {Env}): S \ times E \ rightarrow \ mathbb {R}}$ ${\ displaystyle u (s, \ mathrm {Env}): S \ times E \ rightarrow \ mathbb {R}}$ :

U (s, E nv) = E μ [∑ τ = время T r (τ) ∣ s, E nv] {\ displaystyle u (s, \ mathrm {Env}) = E _ {\ mu} {\ Bigg [} \ sum _ {\ tau = {\ text {time}}} ^ {T} r (\ tau) \ mid s, \ mathrm {Env} {\ Bigg]}}

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

где $r ( t) {\ displaystyle r (t)}$ $r (t)$ - ввод действительного вознаграждения (закодированный в $s (t) {\ displaystyle s (t)}$ $s (t)$ ) во время $t {\ displaystyle t}$ $t$ , $E μ [⋅ ∣ ⋅] {\ displaystyle E _ {\ mu} [\ cdot \ mid \ cdot]}$ ${\ displaystyle E _ {\ mu} [\ cdot \ mid \ cdot]}$ обозначает оператор условного ожидания относительно некоторое, возможно, неизвестное распределение $μ {\ displaystyle \ mu}$ $\ mu$ из набора $M {\ displaystyle M}$ $M$ возможных распределений ( $M {\ displaystyle M }$ $M$ отражает все, что известно о возможных вероятностных реакциях окружающей среды), и упомянутое выше $время = время ⁡ (с) {\ displaystyle {\ text {time}} = \ operatorname { Тим e} (s)}$ ${\ displaystyle {\ text {time}} = \ operatorname {time} (s)}$ - это функция состояния $s {\ displaystyle s}$ $s$ , которая однозначно идентифицирует текущий цикл. Обратите внимание, что мы принимаем во внимание возможность продления ожидаемой продолжительности жизни за счет соответствующих действий.

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

Природа шести приведенных ниже инструкций по модификации доказательства делает невозможным вставку неверной теоремы в доказательство, тем самым упрощая проверку доказательства.

get-axiom ( n)

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

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

применять- rule (k, m, n)

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

delete-Theorem (m)

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

set-switchprog (m, n)

Заменяет switchprog S m: n, при условии, что это непустая подстрока строки S.

check ()

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

DKA = d pore 3 u = d pore 3 8 κ NT π MA {\ displaystyle D_ {KA} = {\ frac {d_ {\ text {pore}}} {3}} u = {\ frac {d _ {\ text {pore}}} {3}} {\ sqrt {\ frac {8 \ kappa NT} {\ pi M_ {A} }}}}

{\ displaystyle 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, если ничего не найдено). Других входов нет. Побочным продуктом максимизации ожидаемого вознаграждения является нахождение кратчайшего пути, который можно найти в течение ограниченного времени с учетом первоначальной ошибки.

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

Как можно быстрее докажите или опровергните, что все даже целое число>2 - сумма двух простых чисел (гипотеза Гольдбаха ). Вознаграждение составляет 1 / t, где t - время, необходимое для производства и проверки первого такого доказательства.

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

A когнитивный робот, которому требуется как минимум 1 литр бензина в час взаимодействует с частично неизвестной средой, пытаясь найти скрытые, ограниченные склады бензина, чтобы время от времени заправлять свой бак. Он награждается пропорционально его продолжительности жизни и умирает самое большее через 100 лет, или как только его резервуар опустеет, или он упадет со скалы, и так далее. Вероятностные реакции окружающей среды изначально неизвестны, но предполагается, что они взяты из аксиоматизированного Speed Prior, согласно которому трудно вычислимые реакции окружающей среды маловероятны. Это позволяет использовать вычислимую стратегию для почти оптимальных прогнозов. Одним из побочных продуктов максимизации ожидаемого вознаграждения является максимальное увеличение ожидаемого срока службы.

См. Также

теоремы Гёделя о неполноте

Ссылки

Внешние ссылки