Аналоговый компьютер общего назначения
Аналоговый компьютер общего назначения ( GPAC ) — это математическая модель аналоговых компьютеров, впервые представленная в 1941 году Клодом Шенноном . [1] Эта модель состоит из схем, в которых несколько основных блоков соединены между собой для вычисления некоторой функции . GPAC может быть реализован на практике с использованием механических устройств или аналоговой электроники . Хотя аналоговые компьютеры были почти забыты из-за появления цифровых компьютеров , GPAC недавно изучался как способ предоставить доказательства физического тезиса Чёрча-Тьюринга . [2] Это связано с тем, что GPAC, как известно, моделирует большой класс динамических систем, определяемых обыкновенными дифференциальными уравнениями , которые часто встречаются в контексте физики . [3] В частности, в 2007 году было показано, что (детерминированный вариант) GPAC эквивалентен с вычислимости точки зрения машинам Тьюринга , тем самым доказывая физический тезис Чёрча-Тьюринга для класса систем, моделируемых GPAC. [4] Недавно это было усилено до полиномиальной эквивалентности по времени. [5]
Определение и история
[ редактировать ]Аналоговый компьютер общего назначения был первоначально представлен Клодом Шенноном . [1] Эта модель возникла в результате его работы над Ванневара Буша , дифференциальным анализатором одним из первых аналоговых компьютеров . [6] Шеннон определил GPAC как аналоговую схему, состоящую из пяти типов модулей: сумматоров (которые складывают свои входные данные), умножителей (которые умножают свои входные данные), интеграторов , постоянных модулей (которые всегда выводят значение 1) и постоянных множителей (которые всегда умножьте их вход на фиксированную константу k ). Совсем недавно, для простоты, вместо этого GPAC был определен с использованием эквивалентных четырех типов единиц: сумматоров, множителей, интеграторов и вещественных констант (которые всегда выводят значение k для некоторого фиксированного действительного числа k ).
В своей оригинальной статье Шеннон представил результат, в котором утверждалось, что функции, вычислимые с помощью GPAC, — это те функции, которые являются дифференциально-алгебраическими .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Шеннон, Клод Э. (1941). «Математическая теория дифференциального анализатора». Журнал математики и физики . 20 (1–4): 337–354. дои : 10.1002/sapm1941201337 .
- ^ О. Бурнес и М.Л. Кампаньоло. Обзор вычислений в непрерывном времени . В новых вычислительных парадигмах. Изменение представлений о том, что вычислимо. (Купер С.Б., Лёве Б. и Сорби А., ред.) Спрингер, стр. 383–423. 2008.
- ^ Д.С. Граса и Дж. Ф. Коста. Аналоговые компьютеры и рекурсивные функции над действительными числами . Журнал сложности , 19(5):644–664, 2003 г.
- ^ О. Бурнес, М.Л. Кампаньоло, Д.С. Граса и Э. Хейнри. Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах . Журнал сложности , 23:317–335, 2007 г.
- ^ Бурне, Оливье; Граса, Дэниел С.; Пули, Амори (2016). Полиномиальное время соответствует решениям полиномиальных обыкновенных дифференциальных уравнений полиномиальной длины: аналоговый компьютер общего назначения и вычислительный анализ являются двумя эффективно эквивалентными моделями вычислений . Международные труды Лейбница по информатике (LIPIcs). Том. 55. Замок Дагштуль. стр. 109:1–109:15. doi : 10.4230/LIPIcs.ICALP.2016.109 . ISBN 9783959770132 . S2CID 1942575 .
- ^ Роберт Прайс (1982). «Клод Э. Шеннон, устная история» . Сеть глобальной истории IEEE . ИИЭЭ . Проверено 14 июля 2011 г.
Внешние ссылки
[ редактировать ]- The Analog Thing : аналоговый компьютер с открытым исходным кодом.