Тезис Черч-Тьюринга и вычислительная мощь нейронных сетей

Тезис Черча-Тьюринга утверждает, что все, что может быть вычислено физически, может быть вычислено на машине Тьюринга. В статье «Аналоговые вычисления через нейронные сети» (Siegelmannn and Sontag, теоретическая информатика , 131: 331–360, 1994; PDF ) утверждается, что нейронная сеть определенной формы (настройки представлены в статье) является более мощной. Авторы говорят, что в экспоненциальном времени их модель может распознавать языки, не поддающиеся вычислению в модели машины Тьюринга.

Разве это не противоречит тезису Черча-Тьюринга?

computability turing-machines church-turing-thesis Джон Р. Л
источник

Ответы:

Нет, это все еще согласуется с тезисом Черча-Тьюринга, их модель снабжена подлинными действительными числами (как в произвольных элементах ), что в значительной степени сразу же расширяет возможности машины Тьюринга. Фактически, заголовок 1.2.2 - это «Значение (не вычислимого) реального веса», где они обсуждают, почему их модель построена так, чтобы включать невычисляемые компоненты. $\mathbb{R}$

На самом деле существует много моделей вычислений, которые превосходят возможности машин Тьюринга (см. Гиперкомпьютер ). Загвоздка в том, что ни один из них, очевидно, не может быть построен в реальном мире (но, возможно, в мире - извините, не смог устоять). $\mathbb{R}$

Люк Мэтисон
источник

+1 хотя бы частично за заключительный каламбур!

Омар

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

всевозможный

Я бы добавил, что

не может существовать в реальном мире из-за привязки Бекенштейна, поэтому QM запрещает такие конструкции.

R

$\mathbb{R}$

Мацей Пехотка

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

R ..

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

Вы не можете произвести резистор ровно . $\mathrm{2\,\Omega}$
Сопротивление изменяется с температурой, а ток, протекающий через резистор, изменит его температуру.
Даже если предположить, что вы знакомы с инженером-электронщиком / колдуном, который может изготовить резисторы с любым точным значением, которое вы выберете, и которые не изменяют сопротивление в зависимости от температуры, для настройки вашего компьютера на неисчислимый язык потребуются неисчислимые значения сопротивления. Таким образом, вы никак не могли бы сказать своему электронщику / колдуну, какое значение сопротивления вам нужно.

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

Возможно, вы захотите принять участие в каких-то правилах-адвокатах и заявить, что кто-то может передать вам одну из этих машин и сказать: «Эй, смотри, эта машина просто имеет правильные значения сопротивления для решения проблемы остановки!» Однако у них нет никакого способа доказать это утверждение, поскольку они не могут измерить компоненты с бесконечной точностью, поэтому лучшее, на что они могут претендовать с обоснованием: «Я проверил это на некотором конечном наборе входных данных, и он правильно решил проблему остановки на эти входы ". Ну, любое конечное подмножество проблемы остановки уже разрешимо по Тьюрингу, так что в этом нет ничего захватывающего.

Дэвид Ричерби
источник