Аналоговый компьютер общего назначения - General purpose analog computer

В Аналоговый компьютер общего назначения (GPAC) математическая модель аналоговые компьютеры впервые представленный в 1941 году Клод Шеннон.[1] Эта модель состоит из цепей, в которых несколько основных узлов соединены между собой, чтобы вычислить немного функция. GPAC может быть реализован на практике за счет использования механические устройства или же аналоговая электроника. Хотя аналоговые компьютеры почти преданы забвению из-за появления цифровой компьютер, GPAC недавно был изучен как способ предоставить доказательства физический тезис Черча – Тьюринга.[2] Это связано с тем, что GPAC также известен как модель большого класса динамические системы определяется с обыкновенные дифференциальные уравнения, которые часто появляются в контексте физика.[3] В частности, в 2007 году было показано, что (детерминированный вариант) GPAC эквивалентен, в вычислимость условия, чтобы Машины Тьюринга, тем самым доказывая физический тезис Черча – Тьюринга для класса систем, моделируемых GPAC.[4]Недавно это было усилено до полиномиальное время эквивалентность.[5]

Определение и история

Аналоговый компьютер общего назначения был первоначально представлен Клод Шеннон.[1] Эта модель появилась в результате его работы над Ванневар Буш с дифференциальный анализатор, рано аналоговый компьютер.[6] Шеннон определил GPAC как аналоговую схему, состоящую из пяти типов блоков: сумматоров (которые складывают свои входы), умножителей (которые умножают свои входы), интеграторы, постоянные единицы (которые всегда выводят значение 1) и постоянные множители (которые всегда умножают свой ввод на фиксированную константу k). Совсем недавно и для простоты GPAC вместо этого был определен с использованием эквивалентных четырех типов единиц: сумматоров, умножителей, интеграторов и единиц действительных констант (которые всегда выводят значение k, для некоторых фиксированных настоящий номер k).

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

Рекомендации

  1. ^ а б Шеннон, Клод Э. (1941). «Математическая теория дифференциального анализатора». Журнал математики и физики. 20 (1–4): 337–354. Дои:10.1002 / sapm1941201337.
  2. ^ О. Борнез и М. Л. Кампаньоло. Обзор непрерывных вычислений времени. В новых вычислительных парадигмах. Изменение представлений о том, что можно вычислить. (Купер С.Б., Лёве Б. и Сорби А., ред.) Springer, страницы 383–423. 2008 г.
  3. ^ Д. С. Граса и Дж. Ф. Коста. Аналоговые компьютеры и рекурсивные функции над вещественными числами. Журнал сложности, 19(5):644–664, 2003
  4. ^ О. Борнез, М. Л. Кампаньоло, Д. С. Граса и Э. Хайнри. Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах. Журнал сложности, 23:317–335, 2007
  5. ^ Борнез, Оливье; Graça, Daniel S .; Пули, Амори (2016). «Полиномиальное время соответствует решениям полиномиальных обыкновенных дифференциальных уравнений полиномиальной длины: аналоговый компьютер общего назначения и вычислительный анализ - две эффективно эквивалентные модели вычислений». Schloss Dagstuhl. Дои:10.4230 / LIPIcs.ICALP.2016.109. Цитировать журнал требует | журнал = (помощь)
  6. ^ Роберт Прайс (1982). "Клод Э. Шеннон, устная история". Сеть глобальной истории IEEE. IEEE. Получено 14 июля, 2011.