Что требуется для универсального аналогового вычисления?

17

Какие операции необходимо выполнить, чтобы выполнить произвольные аналоговые вычисления ? Достаточно ли будет сложение, вычитание, умножение и деление?

Кроме того, кто-нибудь знает точно, какие проблемы можно решить с помощью аналоговых вычислений, но не с цифровыми?

Мэтью Матик
источник
Возможно, вас заинтересует понятие полноты Тьюринга: en.wikipedia.org/wiki/Turing_completeness
Алекс тен Бринк
5
Что вы подразумеваете под аналоговыми вычислениями? Пожалуйста, укажите определение в сообщении или ссылку на определение.
Каве
@Kaveh, до изобретения цифрового компьютера, ученые использовали для расчетов с использованием аналоговых компьютеров, изготовленных из операционных усилителей.
Мухаммед Аль-Туркистани
1
@ Мохаммед, я знаю, что я не прошу историю, я прошу определение. ОП должен либо указывать конкретную модель, либо определять в более общем смысле, что такое модель аналоговых вычислений.
Каве
4
«Универсальность» определяется только в отношении конкретной, формальной, четко определенной модели вычислений. Без такой модели этот вопрос просто без ответа.
Джефф

Ответы:

7

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

Но большинство динамических систем, изучаемых в математике и физике, имеют неисчислимое пространство состояний, например, клеточные автоматы, дифференциальные уравнения, кусочно-линейные отображения и т. Д. Примеры этих систем оказались универсальными. Их проблема остановки имитируется от машины Тьюринга следующим образом. Мы выбираем конкретное счетное семейство начальных состояний и счетное семейство конечных состояний или конечных наборов состояний. Затем задается проблема остановки с начальным состоянием и конечным состоянием / набором состояний, достигнет ли траектория, начинающаяся с начального состояния, конечного состояния / набора состояний. Более конкретные примеры приведены в разделе 7.

Жан-Чарльз Дельвен, Что такое универсальная вычислительная машина ?, Прикладная математика и вычисления, том 215, выпуск 4, 15 октября 2009 года, страницы 1368-1374

Мухаммед Аль-Туркистани
источник
10

Я не думаю, что на этот вопрос можно ответить, если у нас нет определения того, о каких вычислениях мы говорим.

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

2xxИкс


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

Если мы просто математически говорим о классической физике (мы можем установить любую начальную конфигурацию с бесконечной точностью и без каких-либо соображений о таких вещах, как энергия, необходимая для настройки конфигурации, и наблюдать результат аналогично с математической точки зрения), то это было известно в течение длительного времени существуют дифференциальные уравнения для вычислимых функций, и их решение не вычислимо, см. Marian B. Pour-El и J. Ian Richards, « Вычислимость в анализе и физике », 1989.

n>4

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

Кава
источник
4

TL; DR: если под «аналоговыми компьютерами» вы подразумеваете дифференциальные анализаторы , то ответом являются сумматоры, постоянные единицы и интегратор. Bournez, Campagnolo, Graça и Hainry показали в 2006 году ( paywalled / free reprint ), что его идеализированная модель позволяет вычислять все вычисляемые функции в рамках вычислимого анализа , и для этой модели нужны только эти 3 вида единиц.

Трансцендентальные функции

грехехржурнал

Аналоговые вычислительные модели

Как подчеркивали другие, концепция «универсальных вычислений» менее понятна для аналоговых компьютеров, чем для стандартных компьютеров, где различные естественные представления о вычислимости в различных вычислительных моделях были найдены эквивалентными в 1930-х годах (подробности см. На странице Википедии на тему тезиса Чёрча-Тьюринга ). ,

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

Мощность модели GPAC

ΓζY(T)знак равноΓ(T)В течение долгого времени казалось, что такой аналоговый компьютер не является «универсальным», поскольку он не может генерировать некоторые разумные вычислимые функции, используемые математиками.

еY(T)е(Икс)Иксγζ,

В 2013 году Борнез, Граса и Поли показали, что эти аналоговые компьютеры могут эффективно моделировать машину Тьюринга ( стр. 181 большого pdf ), а в 2014 году классы сложности P и NP эквивалентны в этой модели.

Фредерик Гроссханс
источник
3

Было бы полезно предложить, чтобы универсальная аналоговая система могла быть смоделирована бесконечной нейронной сетью, т. Е. Любые другие значения ввода / вывода аналоговой системы могут быть реплицированы согласованной нейронной сетью для данной операции, и операции могут быть при необходимости объединены в цепочку?

Хотя я сам сформулировал эту мысль, последующий поиск показал аналогичное предложение:

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

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

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

(и приношу извинения, если мой взгляд почти мирянина на эту тему явно очевиден)

Jayfang
источник