Насколько полезна полнота по Тьюрингу? полные ли нейронные сети?

Question

Читая некоторые статьи о полноте Тьюринга рекуррентных нейронных сетей (например, вычислимость Тьюринга с нейронными сетями, Хава Т. Зигельманн и Эдуардо Д. Сонтаг, 1991), у меня возникло ощущение, что доказательство, которое было дано там, былоне совсем так практично.Например, упомянутая статья нуждается в нейронной сети, активность нейронов которой должна быть бесконечно точной (чтобы достоверно представлять любое рациональное число).Другие доказательства нуждаются в нейронной сети бесконечного размера.Понятно, что это не так уж и практично.

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

Интересно, что спецификация языка программирования чаще всего оставляет ее открытой, если они завершены или нет.Все сводится к вопросу, смогут ли они всегда выделять больше памяти и будет ли размер стека вызовов функций бесконечным.Большинство спецификаций не определяют это.Конечно, все доступные реализации здесь ограничены, поэтому все практические реализации языков программирования не являются полными по Тьюрингу.

Итак, вы можете сказать, что все компьютерные системы столь же мощны, как и конечные автоматы, и не более того.

И это подводит меня к вопросу: Насколько полезен термин Тьюринг вообще?

И обратно к нейронным сетям: для любого практического применения нейронной сети(включая наш собственный мозг), они не смогут представлять бесконечное число состояний, т.е. по строгому определению полноты по Тьюрингу они не являются полными по Тьюрингу. Так имеет ли смысл вопрос, являются ли нейронные сети полными по Тьюрингу?

На вопрос, являются ли они такими же мощными, как конечные автоматы, был дан ответ уже намного раньше (1954 г., Минский, ответконечно: да) и, кажется, легче ответить.То есть, по крайней мере, теоретически, это было доказательством того, что они такие же мощные, как и любой компьютер.

---

Некоторые другие вопросы, о которых я действительно хочу знать:

• Есть ли теоретический термин, который может сказать что-то более конкретное о вычислительной мощности компьютера?(учитывая ограниченное пространство памяти)

• Как вы можете сравнить вычислительную мощность практических реализаций нейронных сетей с компьютерами?(Полнота Тьюринга бесполезна, как аргументировано выше.)

Answer 1

Смысл заявления о том, что математическая модель является полной по Тьюрингу, заключается в том, чтобы выявить способность модели выполнять любые вычисления, при достаточном количестве ресурсов (т. Е. Бесконечно) , а не показывать, является ли Реализация модели имеет эти ресурсы. Полные модели Тьюринга не смогут обрабатывать конкретный набор вычислений даже при достаточных ресурсах , что показывает разницу в способах работы двух моделей даже при ограниченных ресурсах . Конечно, чтобы доказать это свойство, вы должны предположить, что модели могут использовать бесконечное количество ресурсов, но это свойство модели имеет значение, даже когда ресурсы ограничены .

Answer 2

Полнота по Тьюрингу рекуррентных нейронных сетей может означать: (конечные) таблицы переходов каждой машины Тьюринга (с конечным числом состояний и бесконечной лентой) могут моделироваться конечной рекуррентной нейронной сетью (конечным числом нейроновс конечным числом состояний, особенно только с двумя состояниями).Таблицы переходов определяют три функции:

• следующее состояние (текущее состояние, текущий символ)

• следующий символ (текущее состояние, текущий символ)

• направление (текущее состояние, текущий символ)

Вот как рекуррентная нейронная сеть может выполнить эту задачу(просто очень грубый набросок):

Зеленые нейроны читают символ в текущей ячейке (в двоичном представлении), серые нейроны (изначально отключенные) определяют текущее состояние, красные нейроны записывают новый символ в текущую ячейку, желтые нейроны определяют, идти ли влево или вправо.Синие нейроны - это внутренние нейроны (изначально беззвучные).

Утверждается, , что для каждой машины Тьюринга существует такая рекуррентная нейронная сеть.

IИнтересно, существует ли систематический способ построения такой сети из заданных таблиц переходов?

Answer 3

Когда говорят, что современные компьютеры Turing Complete , существует негласное исключение для описанного бесконечного запоминающего устройства Turing, что, очевидно, невозможно для конечного физического вычислительного устройства.Если вычислительное устройство может делать все, что может делать машина Тьюринга (бесконечная память не выдерживает), то оно Тьюринг завершено для всех практических целей и задач.Благодаря этому менее строгому определению полноты по Тьюрингу , да, возможно, что многие нейронные сети завершены по Тьюрингу .

Конечно, возможно создать такую, которая не Тьюринг завершен .

Answer 4

Чтобы частично ответить на ваш второй вопрос:

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

Answer 5

Обычные нейронные сети с прямой связью не завершены по Тьюрингу . По сути, они эквивалентны одной сложной математической функции, которая может выполнять довольно много вычислений, но не имеет возможности выполнять циклы или другие операции потока управления.

Однако, если вы подключите нейронную сеть каким-либо способом для доступа к среде с состоянием, то ее можно превратить в полную машину Тьюринга .

В качестве наиболее тривиального примера вы можете воссоздать машину Тьюринга в классическом стиле, где:

• вход в нейронную сеть - это значение на ленте и предыдущее состояние
• На выходе нейронной сети происходит следующее состояние и действие

Затем вы можете обучить нейронную сеть для эмуляции действий любой желаемой таблицы / конфигурации состояний машины Тьюринга (возможно, с помощью контролируемого обучения действиям другой машины Тьюринга?)

Примечание. Идея многократного использования сети прямой связи с некоторой формой обратной связи о состоянии по существу эквивалентна рекуррентной нейронной сети . Таким образом, вы можете думать о рекуррентной нейронной сети плюс логика, которая запускает ее многократно как завершенная по Тьюрингу. Вам нужна дополнительная логика (помимо самой сети), чтобы обеспечить полноту по Тьюрингу, потому что необходимо обрабатывать такие вещи, как завершение, повторение и ввод-вывод.

Answer 6

Я думаю, что концепция полноты по Тьюрингу не предназначена для того, чтобы сказать нам, может ли конкретный компьютер выполнить определенную задачу.

Скорее, он предназначен для того, чтобы сказать, способен ли конкретный язык выразить определенную задачу. То есть я бы сказал, что на самом деле выражает алгоритм, а не выполняет это.

Поскольку у нейронных сетей нет языка, речь идет о выражении алгоритма в терминах нейронной сети, а не о возможностях этой сети. Так что я не знаю ответа на последний бит вашего вопроса!

Answer 7

Через много лет позвольте мне самому ответить на этот вопрос.

полнота Тьюринга

• Такой же мощный, как машина Тьюринга (ТМ).
• Требуется бесконечная память . То есть на практике никакое физическое устройство никогда не может быть завершено по Тьюрингу.
• Рассмотрим обычный персональный компьютер (ПК) :
  • Конкретный физический экземпляр - , а не Тьюринг завершен , поскольку он имеет ограниченную память.
  • Однако, рассматривайте концепцию ПК как нечто, где вы можете добавить память по требованию. Все программы будут работать одинаково, если вы добавите больше памяти. Для любого заданного ввода и любой заданной программы существует максимальный объем памяти, который должен работать. (Давайте не будем педантично относиться к пределу int64 адреса памяти или тому подобное. Это технические ограничения, которые могут быть решены, например, большими целыми числами и т. Д.) Таким образом, мы можем сказать, что Концепция ПК Тьюринга завершена .
• Полнота Тьюринга в основном связана с концепцией памяти. Рассмотрим любой конечный автомат / автомат (FSA) и некоторый доступ к внешней памяти. В зависимости от типа памяти вы попадаете в разные классы иерархия Хомского :
  • нет памяти / ограниченная память: обычные языки
  • одиночный стек: автоматы pushdown , языки без контекста
  • два или более стека: полный Тьюринг, рекурсивно перечислимый язык

Рекуррентные нейронные сети (RNN)

Об вычислительной мощности нейронных сетей

Часто цитируется статья О вычислительной мощности нейронных сетей, Siegelmann & Sonntag, 1992 , в которой говорится, что RNNs являются полными по Тьюрингу. В этой статье предполагается, что у нас есть рациональные числа без ограничений в знаменателе / ​​знаменателе, то есть бесконечная память кодируется как рациональные числа или числа с плавающей запятой бесконечной точности. Смотрите также здесь . Обычно мы не моделируем NN способом, который работает с рациональными числами (без ограничений). Когда мы ограничиваемся (R) NN с весами и активациями конечной точности, доказательство в статье падает примерно и больше не применяется. Таким образом, эта статья не так актуальна.

Существует более свежая статья, О практической вычислительной мощности РНН с конечной точностью для распознавания языков, Weiss et al, 2018 , в которой именно это и рассматривается.

Универсальный аппроксиматор

Хорошо известно, что большинство стандартных NN являются универсальными аппроксиматорами . Это говорит о том, что с учетом любой функции (непостоянной, ограниченной и непрерывной) и с учетом некоторого разрешенного порога вы можете построить NN, который приближает эту функцию в пределах допустимого порога. Это о конечномерных векторных пространствах. Когда мы говорим о вычислимости, мы говорим о последовательностях, таким образом, мы имеем бесконечномерное векторное пространство. Таким образом, это свойство не столь актуально.

без внешней памяти

Таким образом, чтобы сформулировать это явно: Без внешней памяти стандарт RNN, а также LSTM - это , не полный по Тьюрингу . Также нет прямого пути, как вы могли бы определить концепцию RNN , где вы могли бы добавить память по требованию. Память RNN - это самые последние скрытые активации. Добавление большего объема памяти означает изменение NN, то есть добавление новых нейронов, тем самым добавляя его внутреннюю работу. Это похоже на изменение самой программы.

с внешней памятью

Существует Neural Turing machine (NTM) и несколько аналогичных моделей, которые имеют какую-то внешнюю память. Здесь просто подумать о концепции NTM , где вы бы добавляли память по требованию. Таким образом, мы можем сказать, что концепция NTM является завершенной по Тьюрингу .

Есть некоторые детали, например, тип внимания, используемый в головах, который требует некоторой адаптации.Существует продолжение этой модели, Дифференцируемый нейронный компьютер (DNC) , который явно решает эту проблему, а также имеет некоторый явный механизм для добавления памяти.

Обучение / тренировка

Мы говорили в основном о теоретической вычислительной мощности.Совсем другой вопрос - может ли NN выучить такую ​​функцию?Т.е. приводит ли обучение (градиентный поиск) к NN, который изучил вычислимую функцию.

Человеческий мозг

Мы могли бы интерпретировать человеческий мозг (или любой мозг) как разновидность сложной нейронной сети,Мы также можем задать вопрос, завершен ли человеческий мозг (модель) по Тьюрингу.Смотрите, например, здесь .Этот вопрос сложный.Интуиция сказала бы, что мы способны выполнять любые вычисления, таким образом, человеческий мозг завершен по Тьюрингу.Однако приведенные здесь аргументы показывают, что RNN не является полным по Тьюрингу.Важным опять же является эффект памяти.В какой-то момент объем памяти человеческого мозга недостаточен для работы на каком-либо входе.Таким образом, нам нужна внешняя память.Итак, человеческий мозг вместе с внешней памятью, по-видимому, завершен по Тьюрингу.

Однако в человеческом мозге есть один аспект памяти, который немного отличается от стандартного RNN: он может обобщаться довысокая степень, и механизм адресации для доступа к определенным активациям отличается.Кроме того, он имеет некоторые адаптивные веса (которые, однако, также могут хранить только конечную информацию).

Answer 8

Я думаю, что важным моментом в машине Тьюринга является то, что для любого заданного ввода и программы, машине понадобится только ограниченное количество ленты, если предположить, что она остановится через некоторое время. Вот почему я бы сказал, что термин «завершение тьюринга» полезен: вам нужна только ограниченная память, чтобы запустить одну конкретную программу тьюринга на каком-то конкретном входе (если программа останавливается). Но если у вас машина / язык / технология, не полная по Тьюрингу, она не сможет моделировать определенные алгоритмы, независимо от того, сколько памяти вы добавляете.

Answer 9

Почти всегда приятно знать, к какому классу в иерархии Хомского относится ваша система.Это особенно важно в более ограниченных классах, таких как обычные языки / конечные автоматы против контекстно-свободных языков.Также важно иметь умение распознавать, к какому классу относится ваша проблема, которую вы пытаетесь решить, иначе можно попытаться сделать глупые вещи, такие как анализ HTML или XML только с помощью регулярных выражений, что невозможно.

Если вы знаете, что ваш формализм или система завершены, вы заявляете, что вы можете построить с ней все, что захотите.Это ничего не говорит о практичности, просто о возможности или невозможности решения проблем.Это болезненно верно при рассмотрении тарпинтинга Тьюринга, но есть также много комплексных систем Тьюринга, которые специально созданы для нишевых целей, о которых никто никогда не мечтает использовать для работы общего назначения в производственных условиях.хорошее знание иерархии Хомского поможет вам в очень многих ситуациях, не только для выбора правильного типа парсера;regexp, pushdown, CFG или более мощный, но также для выбора правильного типа машины или формализма для выражения процессов в целом.

Answer 10

Ответ очень прост. Если вы можете эмулировать с ним ворота NOR или NAND, то это Turing Complete, предполагая, что все остальное - просто вопрос объединения вещей.