Какие операции необходимо выполнить, чтобы выполнить произвольные аналоговые вычисления ? Достаточно ли будет сложение, вычитание, умножение и деление?
Кроме того, кто-нибудь знает точно, какие проблемы можно решить с помощью аналоговых вычислений, но не с цифровыми?
computability
computation-models
turing-completeness
Мэтью Матик
источник
источник
Ответы:
К сожалению, в аналоговых вычислениях не существует «универсальной» концепции универсальности. Тем не менее, эта статья Delvenne предлагает объединяющий формализм универсальности в дискретных (например, машинах Тьюринга) и непрерывных (например, дифференциальных уравнениях) динамических системах и рассматривает некоторые универсальные системы, изученные в литературе. Вот выдержка из статьи, в которой неформально описывается процедура доказательства универсальности динамической системы:
Жан-Чарльз Дельвен, Что такое универсальная вычислительная машина ?, Прикладная математика и вычисления, том 215, выпуск 4, 15 октября 2009 года, страницы 1368-1374
источник
Я не думаю, что на этот вопрос можно ответить, если у нас нет определения того, о каких вычислениях мы говорим.
Универсальность модели машины по классу вычислений означает, что любые вычисления в этом классе могут быть вычислены машиной. Если вы не определите класс «произвольных аналоговых вычислений», мы не сможем ответить, что для них является универсальностью.
Если ваш вопрос заключается в том, существуют ли физические системы, которые, начиная с начального состояния, через какое-то время достигнут другого состояния, и если это всегда вычислимо, то ответ зависит от того, о какой физике мы говорим, и что это означает для настройки исходная конфигурация и наблюдение за результатом и т. д.
Если мы просто математически говорим о классической физике (мы можем установить любую начальную конфигурацию с бесконечной точностью и без каких-либо соображений о таких вещах, как энергия, необходимая для настройки конфигурации, и наблюдать результат аналогично с математической точки зрения), то это было известно в течение длительного времени существуют дифференциальные уравнения для вычислимых функций, и их решение не вычислимо, см. Marian B. Pour-El и J. Ian Richards, « Вычислимость в анализе и физике », 1989.
Как правило, если мы можем просто проверить равенство двух действительных чисел, которое дает функцию, которая не является непрерывной, с типичными типологиями информации о действительных числах и, следовательно, не может быть вычислена машиной Тьюринга, поскольку любая функция (включая функции более высокого типа) является машиной Тьюринга Можно вычислять непрерывно (относительно топологии информации).
источник
TL; DR: если под «аналоговыми компьютерами» вы подразумеваете дифференциальные анализаторы , то ответом являются сумматоры, постоянные единицы и интегратор. Bournez, Campagnolo, Graça и Hainry показали в 2006 году ( paywalled / free reprint ), что его идеализированная модель позволяет вычислять все вычисляемые функции в рамках вычислимого анализа , и для этой модели нужны только эти 3 вида единиц.
Трансцендентальные функции
Аналоговые вычислительные модели
Как подчеркивали другие, концепция «универсальных вычислений» менее понятна для аналоговых компьютеров, чем для стандартных компьютеров, где различные естественные представления о вычислимости в различных вычислительных моделях были найдены эквивалентными в 1930-х годах (подробности см. На странице Википедии на тему тезиса Чёрча-Тьюринга ). ,
Чтобы определить такую универсальность, нужно сначала определить хорошую модель для аналоговых вычислений, и это трудная задача, поскольку модель должна быть идеализированной и достаточно естественной, чтобы быть полезной, но ее идеализация не должна давать нереалистичную силу модель. Примером такой хорошей идеализации является бесконечная лента машин Тьюринга. Проблема с аналоговыми компьютерами связана с реальными числами, которые могут позволить создавать неразумные вещи, такие как машина Zeno . Тем не менее, несколько таких моделей были предложены и использованы в литературе (GPAC является основной темой этого ответа, но я стараюсь быть полным в списке ниже, без какого-либо гиперкомпьютера ):
Мощность модели GPAC
В 2013 году Борнез, Граса и Поли показали, что эти аналоговые компьютеры могут эффективно моделировать машину Тьюринга ( стр. 181 большого pdf ), а в 2014 году классы сложности P и NP эквивалентны в этой модели.
источник
Было бы полезно предложить, чтобы универсальная аналоговая система могла быть смоделирована бесконечной нейронной сетью, т. Е. Любые другие значения ввода / вывода аналоговой системы могут быть реплицированы согласованной нейронной сетью для данной операции, и операции могут быть при необходимости объединены в цепочку?
Хотя я сам сформулировал эту мысль, последующий поиск показал аналогичное предложение:
Возможно, тогда все, что вам нужно, это примитивные операции для перемещения значения из одного узла в другой. Отключите манжету, которая может быть плюс, минус и разделить, чтобы получить соотношение между соединениями.
Теперь, что касается неразрешимых проблем, посмотрите, где нейронные сети были успешно применены или выполняются из-за того, что реализованы на отдельном компьютере.
(и приношу извинения, если мой взгляд почти мирянина на эту тему явно очевиден)
источник