범용 아날로그 컴퓨터

General purpose analog computer

범용 아날로그 컴퓨터(GPAC)는 클로드 섀넌이 1941년 처음 도입한 아날로그 컴퓨터의 수학 모델이다.[1] 이 모델은 일부 기능을 계산하기 위해 몇 개의 기본 장치가 상호 연결된 회로로 구성된다. GPAC는 기계장치나 아날로그 전자장치를 이용하여 실제로 구현될 수 있다. 디지털 컴퓨터의 출현으로 아날로그 컴퓨터가 거의 망각 상태에 빠졌지만, 최근에는 물리적인 Church-Turing 논문의 증거를 제공하는 방법으로 GPAC가 연구되고 있다.[2] 이는 GPAC가 물리학의 맥락에서 자주 나타나는 일반적인 미분방정식으로 정의한 많은 종류의 동적 시스템을 모델링하는 것으로도 알려져 있기 때문이다.[3] 특히 2007년에 (의 결정론적 변종) GPAC가 계산성 측면에서 튜링 기계와 동등하다는 것을 보여줌으로써 GPAC가 모델링한 시스템 클래스에 대한 물리적 Church-Turing 논문이 입증되었다.[4] 이것은 최근에 다항식 시간 등가로 강화되었다.[5]

정의 및 이력

범용 아날로그 컴퓨터는 원래 Claude Shannon에 의해 도입되었다.[1] 이 모델은 초기 아날로그 컴퓨터인 Vannevar Bush의 차동 분석기에 대한 연구 결과 나왔다.[6] 섀넌은 GPAC를 5가지 유형의 아날로그 회로로 정의했다. 즉, 애더(입력을 추가하는), 멀티플라이어(입력을 곱하는 멀티플라이어), 통합자, 상수 단위(항상 값을 출력하는 멀티플라이어), 상시 멀티플라이어(입력을 항상 고정 상수 k로 곱하는 멀티플라이어)이다. 보다 최근에, 그리고 단순성을 위해, GPAC는 대신 애더더, 승수, 통합자 및 실제 상수 단위(일부 고정된 실제 수 k에 대해 항상 값 k를 출력한다)의 등가 4가지 유형의 단위를 사용하여 정의되었다.

섀넌은 원래 논문에서 GPAC가 계산할 수 있는 함수는 차등 대수학이라는 결과를 제시했다.

참조

  1. ^ a b Shannon, Claude E. (1941). "Mathematical Theory of the Differential Analyzer". Journal of Mathematics and Physics. 20 (1–4): 337–354. doi:10.1002/sapm1941201337.
  2. ^ O. 본즈와 M. L. 캄파뇰로. 연속 시간 계산에 관한 조사. 새로운 컴퓨팅 패러다임에서. 계산 가능한 개념 변경. (쿠퍼, S.B.와 뢰베, B.와 소르비, A., 에드) 스프링거, 383-423. 2008.
  3. ^ D. S. 그라사와 J. F. 코스타, 아날로그 컴퓨터와 리얼리티에 대한 재귀적 기능. 복잡성 저널, 19:644–664, 2003
  4. ^ O. 본즈, M. L. 캄파뇰로, D. S. 그라사, E. 하이니. 다항식 미분방정식은 계산 가능한 콤팩트 간격에서 계산 가능한 모든 실제 함수를 계산한다. 복잡성 저널, 2007년 23:317–335
  5. ^ Bournez, Olivier; Graça, Daniel S.; Pouly, Amaury (2016). "Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length: The General Purpose Analog Computer and Computable Analysis Are Two Efficiently Equivalent Models of Computations". Schloss Dagstuhl. doi:10.4230/LIPIcs.ICALP.2016.109. S2CID 1942575. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  6. ^ Robert Price (1982). "Claude E. Shannon, an oral history". IEEE Global History Network. IEEE. Retrieved July 14, 2011.