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

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

Машина Гёделя часто обсуждается при рассмотрении вопросов метаобучения , также известного как «обучение обучению». Приложения включают в себя автоматизацию решений, принимаемых человеком, и передачу знаний между множеством связанных задач, что может привести к разработке более надежных и общих архитектур обучения. ^{[ 5 ]} Хотя теоретически это возможно, полная реализация еще не создана. ^{[ 6 ]}

Машину Гёделя часто сравнивают с Маркуса Хаттера , AIXI еще одной формальной спецификацией общего искусственного интеллекта . Шмидхубер отмечает, что машина Гёделя могла бы начать с реализации 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\rightarrow \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$ возможных распределений ( $M$ отражает все, что известно о возможных вероятностных реакциях окружающей среды), а упомянутое выше ${\text{time}}=\operatorname {time} (s)$ это функция государства $s$ который однозначно идентифицирует текущий цикл. ^{[ 3 ]} Отметим, что мы учитываем возможность продления ожидаемого срока службы соответствующими действиями. ^{[ 3 ]}

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

Природа шести инструкций по изменению доказательства, приведенных ниже, делает невозможным вставить в доказательство неверную теорему, упрощая тем самым проверку доказательства. ^{[ 3 ]}

получить-аксиому ( n )

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

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

применить-правило( k , m , n )

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

удалить-теорему( м )

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

set-switchprog( m , n )

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

проверять()

Проверяет, достигнута ли цель поиска доказательства. Целевая теорема утверждает, что при текущей аксиоматизированной функции полезности u (пункт 1f) полезность переключения с p на текущую программу переключения будет выше, чем полезность продолжения выполнения p (которая будет продолжать поиск альтернативных программ переключения). ^{[ 3 ]}

теорема состояния2( m , n )

Принимает два аргумента, m и n , и пытается преобразовать содержимое S _m:n в теорему.

Примеры приложений

Ограниченная по времени NP-жесткая оптимизация

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

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

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

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

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

См. также

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

Ссылки

^ Махмуд, М.М. Хасан (2008). Универсальное трансферное обучение . стр. 16–18. ISBN 9780549909880 .
^ Андерсон, Майкл Л.; Тим Оутс (весна 2007 г.). «Обзор недавних исследований в области метарассуждения и метаобучения» . Журнал ИИ . 28 (1): 7.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Шмидхубер, Юрген (декабрь 2006 г.). Машины Гёделя: самореферентные ¨ универсальные решатели задач, осуществляющие доказуемо оптимальные самоусовершенствования (PDF) . Проверено 10 ноября 2014 г. ^{[ постоянная мертвая ссылка ]}
^ «Машина Гёделя» .
^ Шауль, Том; Шмидхубер, Юрген (2010). «Металобучение» . Схоларпедия . 5 (6): 4650. Бибкод : 2010SchpJ...5.4650S . doi : 10.4249/scholarpedia.4650 .
^ Стьюнебринк, Басс Р.; Шмидхубер, Юрген (2011). «Семейство реализаций машины Гёделя». Общий искусственный интеллект . Конспекты лекций по информатике. Полный. 6830. стр. 275–280. CiteSeerX 10.1.1.300.3076 . дои : 10.1007/978-3-642-22887-2_29 . ISBN 978-3-642-22886-5 .
^ Jump up to: ^а ^б ^с Шмидхубер, Юрген (5 марта 2009 г.). «Высшее познание в Гёделе» (PDF) . Когнитивные вычисления . 1 (2): 177–193. CiteSeerX 10.1.1.218.3323 . дои : 10.1007/s12559-009-9014-y . S2CID 10784194 . Проверено 13 ноября 2014 г.

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

Домашняя страница машины Gödel

[1] Махмуд, М.М. Хасан (2008). Универсальное трансферное обучение . стр. 16–18. ISBN 9780549909880 .

[2] Андерсон, Майкл Л.; Тим Оутс (весна 2007 г.). «Обзор недавних исследований в области метарассуждения и метаобучения» . Журнал ИИ . 28 (1): 7.

[Gödel_Machines.-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Шмидхубер, Юрген (декабрь 2006 г.). Машины Гёделя: самореферентные ¨ универсальные решатели задач, осуществляющие доказуемо оптимальные самоусовершенствования (PDF) . Проверено 10 ноября 2014 г. ^{[ постоянная мертвая ссылка ]}

[4] «Машина Гёделя» .

[5] Шауль, Том; Шмидхубер, Юрген (2010). «Металобучение» . Схоларпедия . 5 (6): 4650. Бибкод : 2010SchpJ...5.4650S . doi : 10.4249/scholarpedia.4650 .

[6] Стьюнебринк, Басс Р.; Шмидхубер, Юрген (2011). «Семейство реализаций машины Гёделя». Общий искусственный интеллект . Конспекты лекций по информатике. Полный. 6830. стр. 275–280. CiteSeerX 10.1.1.300.3076 . дои : 10.1007/978-3-642-22887-2_29 . ISBN 978-3-642-22886-5 .

[ultimate-7] Jump up to: ^а ^б ^с Шмидхубер, Юрген (5 марта 2009 г.). «Высшее познание в Гёделе» (PDF) . Когнитивные вычисления . 1 (2): 177–193. CiteSeerX 10.1.1.218.3323 . дои : 10.1007/s12559-009-9014-y . S2CID 10784194 . Проверено 13 ноября 2014 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]