2014/04/01 by Ed Blakey · 1 voice
Computer Science · #cs.CC
paper · pdf · doi:10.4204/eptcs.143.3
published as EPTCS 143, 2014, pp. 32-40 · In Proceedings DCM 2012, arXiv:1403.7579
arxiv created 2014/04/01 · arxiv published 2014/04/01 · arxiv updated 2014/04/02
We recall from previous work a model-independent framework of computational complexity theory. Notably for the present paper, the framework allows formalization of the issues of precision that present themselves when one considers physical, error-prone (especially analogue rather than digital) computational systems. We take as a case study the ray-tracing problem, a Turing-machine-incomputable problem that can, in apparent violation of the Church-Turing thesis, nonetheless be said to be solved by certain optical computers; however, we apply the framework of complexity theory so as to formalize the intuition that the purported super-Turing power of these computers in fact vanishes once precision is properly considered.