Читая некоторые статьи о полноте Тьюринга рекуррентных нейронных сетей (например, вычислимость Тьюринга с нейронными сетями, Хава Т. Зигельманн и Эдуардо Д. Сонтаг, 1991), у меня возникло ощущение, что доказательство, которое было дано там, былоне совсем так практично.Например, упомянутая статья нуждается в нейронной сети, активность нейронов которой должна быть бесконечно точной (чтобы достоверно представлять любое рациональное число).Другие доказательства нуждаются в нейронной сети бесконечного размера.Понятно, что это не так уж и практично.
Но я начал задаваться вопросом, имеет ли смысл вообще просить о полноте по Тьюрингу.По строгому определению, ни одна компьютерная система в настоящее время не является полной по Тьюрингу, потому что ни одна из них не сможет симулировать бесконечную ленту.
Интересно, что спецификация языка программирования чаще всего оставляет ее открытой, если они завершены или нет.Все сводится к вопросу, смогут ли они всегда выделять больше памяти и будет ли размер стека вызовов функций бесконечным.Большинство спецификаций не определяют это.Конечно, все доступные реализации здесь ограничены, поэтому все практические реализации языков программирования не являются полными по Тьюрингу.
Итак, вы можете сказать, что все компьютерные системы столь же мощны, как и конечные автоматы, и не более того.
И это подводит меня к вопросу: Насколько полезен термин Тьюринг вообще?
И обратно к нейронным сетям: для любого практического применения нейронной сети(включая наш собственный мозг), они не смогут представлять бесконечное число состояний, т.е. по строгому определению полноты по Тьюрингу они не являются полными по Тьюрингу. Так имеет ли смысл вопрос, являются ли нейронные сети полными по Тьюрингу?
На вопрос, являются ли они такими же мощными, как конечные автоматы, был дан ответ уже намного раньше (1954 г., Минский, ответконечно: да) и, кажется, легче ответить.То есть, по крайней мере, теоретически, это было доказательством того, что они такие же мощные, как и любой компьютер.
Некоторые другие вопросы, о которых я действительно хочу знать:
Есть ли теоретический термин, который может сказать что-то более конкретное о вычислительной мощности компьютера?(учитывая ограниченное пространство памяти)
Как вы можете сравнить вычислительную мощность практических реализаций нейронных сетей с компьютерами?(Полнота Тьюринга бесполезна, как аргументировано выше.)