物理可计算理论

近年来,将物理过程本身看作计算、用物理过程代替Turing机算法的想法,伴随着量子计算和其他一些非传统计算模式（例如DNA计算）的研究得到了一定程度的发展.然而由于概念上的不明晰,使得关于这类计算理论的复杂性评估一直处于含糊不清、模棱两可的状态.本文对输入／输出进行了统一，对物理实验的三个关键步骤：制备、演化和测量作了数学上的刻画，并由此引出物理可计算的形式定义（包括确定性的和非确定性的）．在此基础上给出了资源复杂性的概念，本文的资源是指一个物理过程消耗的总资源，不但包括了时间和空间，还包括了质量和能量．对于某个物理计算方法，相应的复杂性则描述了资源关于输入长度的增长情况．在这套形式理论中，以往非形式的“物理可计算”的例子可以在其中得到形式化地表达、且可作严格的复杂度分析．作为例子，考察了均值的统计力学求法、DNA计算和量子计算．在经典Church-Turing论题方面，对于前人试图用物理方法超越经典Turing机计算能力的著名例子，本文也在上述的理论框架下对它们的能行性进行了考察．我们认定：现有的这些例子因不能在有穷资源的限制内得到计算结果，从而都是无效的．

Physical Computation Theory

With the progress of the research in Quantum Computation and other unconventional forms of computations(e.g.DNA computation),the idea that one can just look physical procedures themselves as computations,or more precisely,one can solve a problem by substituting specific physical procedures Turing machines has also been developed.However,because of the obscurity in its fundamental concepts,this theory so far actually remains quite ambiguous and makes people hard to analyze. In this paper,we unify the forms of input/output,strictly describe the three crucial parts of all physical experiments: initialization,evolution and measurement,and then,introduce a formal definition of physical computation(including the deterministic version and the probabilistic version).Based on this,the concept of physical complexity is given,which includes energy and mass as two new fundamental resources in addition to the classical ones: time and space.So the complexity qualifies the amount of these 4 resources with respect to the length of input.As examples,we have analyzed DNA computation,Quantum computation and a famous example-Calculating average of three numbers using statistical physics,due to Pitowsky. Besides,the issues about the computability of some classical non-computable functions under physical computation are also discussed in this paper.We conclude,that all of the examples discussed in this paper fail to outdo universal Turing machine in computability,considering the infinite resources they cost before obtaining the correct answer.