Ответ 1

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

Ответ 2

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

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

• next-symbol (current-state, current-symbol)

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

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

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

Существует более поздняя статья " О практической вычислительной мощности конечных прецизионных RNN для распознавания языков", Weiss et al, 2018, в которой именно об этом говорится.

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 10

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

Языки, не относящиеся к Тьюрингу, значительно более эффективны.

Ответ 11

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