
浏览全部资源
扫码关注微信
南京大学计算机科学与技术系
纸质出版日期:2012-01-01,
移动端阅览
[1]郑惠民,宋方敏.物理可计算理论[J].武汉大学学报(理学版),2012,58(01):73-80.
ZHENG HUIMIN, SONG FANGMIN. Physical Computation Theory. [J]. 2012, 58(1): 73-80.
[1]郑惠民,宋方敏.物理可计算理论[J].武汉大学学报(理学版),2012,58(01):73-80. DOI: 10.14188/j.1671-8836.2012.01.015.
ZHENG HUIMIN, SONG FANGMIN. Physical Computation Theory. [J]. 2012, 58(1): 73-80. DOI: 10.14188/j.1671-8836.2012.01.015.
近年来
将物理过程本身看作计算、用物理过程代替Turing机算法的想法
伴随着量子计算和其他一些非传统计算模式(例如DNA计算)的研究得到了一定程度的发展.然而由于概念上的不明晰
使得关于这类计算理论的复杂性评估一直处于含糊不清、模棱两可的状态.
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.
量子计算物理可计算计算复杂度
quantum computationphysical computationcomputational complexity
0
浏览量
121
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621