Насколько полезный полнота по Тьюрингу? нейронные сети Тьюринг завершены?
Читая некоторые газеты о полноте по Тьюрингу текущих нейронных сетей (например: исчисляемость Turing с нейронными сетями, Hava T. Siegelmann и Eduardo D. Sontag, 1991), я получил чувство, что доказательство, которое было дано, там не было действительно настолько практично. Например, бумаге, на которую ссылаются, нужна нейронная сеть, какое действие нейрона должно иметь точность бесконечности (к надежному, представляют любое рациональное число). Другим доказательствам нужна нейронная сеть бесконечного размера. Очевидно, это не действительно настолько практично.
Но я начал задаваться вопросом теперь, имеет ли действительно смысл вообще просить полноту по Тьюрингу. По строгому определению никакая компьютерная система в наше время не полна по Тьюрингу, потому что ни один из них не сможет моделировать бесконечную ленту.
Интересно, спецификация языка программирования оставляет его, чаще всего открываются, если они - завершенный Тьюринг или нет. Все это сводится к вопросу, если они будут всегда мочь выделить больше памяти и если размер стопки вызова функции бесконечен. Большая часть спецификации действительно не указывает это. Конечно, все доступные реализации ограничены здесь, таким образом, все практические реализации языков программирования не полны по Тьюрингу.
Так, что можно сказать, то, что все компьютерные системы просто одинаково мощны как конечные автоматы и не больше.
И это приносит мне к вопросу: Как полезный действительно ли термин полон по Тьюрингу вообще?
И назад к нейронным сетям: Для любой практической реализации нейронной сети (включая наш собственный мозг), они не смогут представить бесконечное число состояний, т.е. по строгому определению полноты по Тьюрингу, они не полны по Тьюрингу. Вопрос, если нейронные сети полны по Тьюрингу, имеют смысл вообще?
На вопрос, если они так же мощны как конечные автоматы, ответили уже намного ранее (1954 Minsky, ответ, конечно: да), и также кажется легче ответить. Т.е. по крайней мере в теории, которая уже была доказательством, что они так же мощны как любой компьютер.
Некоторые другие вопросы, которые являются больше, о каком я действительно хочу знать:
Есть ли какой-либо теоретический термин, который может сказать что-то более определенное относительно вычислительной мощности компьютера? (учитывая его пространство ограниченной памяти)
Как можно сравнить вычислительную мощность практических реализаций нейронных сетей с компьютерами? (Полнота по Тьюрингу не полезна как argumented выше.)
7 ответов
Смысл утверждения, что математическая модель является полной по Тьюрингу, заключается в том, чтобы показать способность модели выполнять любые вычисления, при наличии достаточного количества ресурсов (т.е. бесконечного), а не в том, чтобы показать, обладает ли конкретная реализация модели этими ресурсами. Неполные по Тьюрингу модели не смогут справиться с определенным набором вычислений, даже при достаточном количестве ресурсов, что показывает разницу в способе работы двух моделей, даже когда они имеют ограниченные ресурсы. Конечно, чтобы доказать это свойство, нужно предположить, что модели способны использовать бесконечное количество ресурсов, но это свойство модели актуально даже тогда, когда ресурсы ограничены.
Почти всегда приятно знать, к какому классу в иерархии Хомского относится ваша система. Это особенно важно в более узких классах, таких как обычные языки / конечные автоматы против контекстно-свободных языков. Также важно иметь умение распознавать, в каком классе находится ваша проблема, которую вы пытаетесь решить, иначе можно попытаться делать глупые вещи, такие как синтаксический анализ HTML или XML только с помощью регулярных выражений, что невозможно.
Знание того, что ваш формализм или система завершены по Тьюрингу, говорит о том, что с их помощью вы можете построить все, что захотите. Здесь ничего не говорится о практичности, просто о возможности или невозможности решения проблемы. Это до боли верно, когда речь идет о брезентах Тьюринга, но есть также много полных систем Тьюринга, которые специально созданы для нишевых целей, и никому даже не следует мечтать об их использовании для работы общего назначения в производственных условиях.
Короче говоря, хорошее знание иерархии Хомского поможет вам во многих ситуациях, не только для выбора правильного типа синтаксического анализатора; regexp, pushdown, CFG или более мощные, но также для выбора правильного типа машины или формализма для выражения процессов в целом.
Чтобы частично ответить на ваш второй вопрос:
Нейронные сети обладают свойством быть универсальными аппроксиматорами , то есть они могут аппроксимировать любую функцию с произвольной степенью точности. Это часть «степени точности», которая не дает нейронной сети быть бесконечной.
Я думаю, что концепция полноты по Тьюрингу не предназначена для того, чтобы сказать нам, может ли конкретный компьютер выполнять определенную задачу.
Скорее, он предназначен для того, чтобы сказать, способен ли конкретный язык выразить конкретную задачу. То есть, я бы сказал, что на самом деле речь идет о выражении алгоритма, не выполняющего его.
Поскольку у нейронных сетей нет языка, вопрос заключается в выражении алгоритма в терминах нейронной сети, а не в ее возможностях. Так что я не знаю ответа на последний вопрос вашего вопроса!
Я думаю, что важным моментом в машине Тьюринга является то, что для любого данного ввода и программы машине потребуется только конечное количество ленты, предполагая, что она остановится через некоторое время. Вот почему я бы сказал, что термин "полная машина Тьюринга" полезен: Вам нужна только конечная память, чтобы выполнить одну конкретную тьюринговски полную программу на некоторых конкретных входных данных (если программа остановится). Но если у вас есть неполная по Тьюрингу машина/язык/технология, она не сможет имитировать определенные алгоритмы, независимо от того, сколько памяти вы добавите.
Когда говорят, что современные компьютеры являются Turing Complete, делается негласное исключение для бесконечного устройства хранения данных, описанного Тьюрингом, что очевидно является невозможностью для конечного физического вычислительного устройства. Если вычислительное устройство может делать все, что может делать машина Тьюринга (без учета бесконечного хранилища), то оно является полным по Тьюрингу для всех практических намерений и целей. Согласно этому менее строгому определению полноты Тьюринга, да, возможно, что многие нейронные сети являются полными по Тьюрингу.
Конечно, можно создать такую, которая не является полной по Тьюрингу.
В основном это означает, что с языком программирования или архитектурой, которые являются полными по Тьюрингу
вы можете выполнять самые разнообразные алгоритмы... в основном - любые.
Нетьюринговские языки значительно более узкие по потенциалу.