物理可计算理论

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