stringtranslate.com

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ ab Шеннон, Клод Э. (1941). «Математическая теория дифференциального анализатора». Журнал математики и физики . 20 (1–4): 337–354. doi :10.1002/sapm1941201337.
  2. ^ О. Бурнез и М. Л. Кампаньоло. Обзор вычислений в непрерывном времени. В новых вычислительных парадигмах. Изменение концепций того, что вычислимо. (Cooper, SB и Löwe, B. и Sorbi, A., ред.) Springer, страницы 383–423. 2008.
  3. ^ DS Graça и JF Costa. Аналоговые компьютеры и рекурсивные функции над вещественными числами. Journal of Complexity , 19(5):644–664, 2003
  4. ^ O. Bournez, ML Campagnolo, DS Graça и E. Hainry. Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах. Journal of Complexity , 23:317–335, 2007
  5. ^ Бурне, Оливье; Граса, Даниэль С.; Пули, Амори (2016). Полиномиальное время соответствует решениям полиномиальных обыкновенных дифференциальных уравнений полиномиальной длины: аналоговый компьютер общего назначения и вычислимый анализ — две эффективно эквивалентные модели вычислений . Международные труды Лейбница по информатике (LIPIcs). Т. 55. Schloss Dagstuhl. С. 109:1–109:15. doi : 10.4230/LIPIcs.ICALP.2016.109 . ISBN 9783959770132. S2CID  1942575.
  6. ^ Роберт Прайс (1982). «Клод Э. Шеннон, устная история». IEEE Global History Network . IEEE . Получено 14 июля 2011 г.

Внешние ссылки