실제 연산
Real computation
계산가능성 이론에서, 실제 계산 이론은 무한정 정밀한 실수를 이용한 가상 계산 기계를 다룬다.그들은 실수로 작동하기 때문에 이 이름이 붙여졌다.이 이론 내에서는 "만델브로트 세트의 보완은 부분적으로만 해독할 수 있다"와 같은 흥미로운 진술들을 증명할 수 있다.
이 가상의 컴퓨터 기계들은 실제 숫자로 작동하는 이상적인 아날로그 컴퓨터로 볼 수 있는 반면, 디지털 컴퓨터는 계산 가능한 숫자로 제한된다.그것들은 차등 모델과 대수 모델로 더 세분될 수 있다(이 맥락에서 디지털 컴퓨터는 적어도 계산 가능한 실제에 대한 연산에 관한[1] 한 위상학적으로 간주되어야 한다).이는 선택된 모델에 따라 실제 컴퓨터가 디지털 컴퓨터에서 뺄 수 없는 문제를 해결할 수 있게 할 수도 있다(예를 들어, 하바 시겔만의 신경망은 비컴퓨팅 실제 무게를 가질 수 있어 비복구 언어를 계산할 수 있다). 또는 그 반대의 경우도 있다.(클로드 섀넌의 이상화된 아날로그 컴퓨터는 대수적 차이점만 해결할 수 있다.디지털 컴퓨터가 약간의 초월 방정식도 해결할 수 있다.그러나 Claude Shannon의 이상화된 아날로그 컴퓨터 연산, 즉 계산은 실시간으로 이루어지기 때문에 이 비교는 완전히 공평하지 않다.섀넌의 모델은 이 문제에 대처하기 위해 개조될 수 있다.)[2]
실제에 대한 계산의 표준 모델은 블럼-이다.슈브-스마일 기계(BSS).
실제 연산이 물리적으로 실현 가능하다면, 다항 시간 내에 NP-완전 문제, 심지어 #P-완전 문제까지도 해결할 수 있을 것이다.물리적 우주의 무한한 정밀 실수는 홀로그램 원리와 베켄슈타인 제본에 의해 금지된다.[3]
참고 항목
- 하이퍼컴퓨팅, 이렇게 강력한 다른 기계들을 위한.
참조
- ^ Klaus Weihrauch (1995). A Simple Introduction to Computable Analysis.
- ^ O. Bournez; M. L. Campagnolo; D. S. Graça & E. Hainry (Jun 2007). "Polynomial differential equations compute all real computable functions on computable compact intervals". Journal of Complexity. 23 (3): 317–335. doi:10.1016/j.jco.2006.12.005.
- ^ Scott Aaronson, NP-완전한 문제와 물리적 현실, ACM SIGACT 뉴스, 제36권, 제1권(2005년 3월), 페이지 30~52.
추가 읽기
- Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale (1998). Complexity and Real Computation. ISBN 0-387-98281-7.
{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크) - Campagnolo, Manuel Lameiras (July 2001). Computational complexity of real valued recursive functions and analog circuits. Universidade Técnica de Lisboa, Instituto Superior Técnico.
- Natschläger, Thomas, Wolfgang Maass, Henry Markram. The "Liquid Computer" A Novel Strategy for Real-Time Computing on Time Series (PDF).
{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크) - Siegelmann, Hava (December 1998). Neural Networks and Analog Computation: Beyond the Turing Limit. ISBN 0-8176-3949-7.
- Siegelmann, Hava & Sontag, Eduardo D. On The Computational Power Of Neural Nets.[영구적 데드링크]
