主题：【25个科学问题征文】常规计算的极限是什么？ -- 电子狼

共:💬13 🌺11

老大河待整

全看树展主题 · 分页首页上页下页末页

家园

【25个科学问题征文】常规计算的极限是什么？

外链出处

Charles Seife

常规计算的极限是什么？

粗略一看，计算的最终极限似乎是个工程学问题。芯片可以加载多少能量（用于计算）而不烧掉它？存储器里的一位比特能翻转多快？计算机能做多大，且仍能放在房间里？这些问题看上去不是那么深刻。

实际上，计算本身远远比如何造好一个计算机要抽象和根本的多。这个认知形成于30年代中期，当普林斯顿数学家阿伦佐.丘奇（Alonzo Church）和阿兰.图灵（Alan Turing）证明了一个定理，简要说来是：任何以比特(bits)和字节（bytes)为基础的计算问题可以用一个理想计算机（图灵机）实现。通过证明所有的常规计算机在本质上是相近的，使得科学家和数学家可以探讨关于计算的本质问题，而不会陷入计算机架构上的细微末节之中。

举例来说，理论数学家现在可以把计算问题分为几个大类。P问题指那些大致来说可以很快解决的简单问题，譬如把一组名字按字母顺序排序。NP问题难以解决，但验证解答比找到解答相对容易。NP问题的一个例子是旅行推销员路线问题：找到遍历一系列地点的最短路线。对此所有已知的算法都需要很多的计算步骤，以至于对相对很少节点的情形，现在的所有常规计算机也难以胜任。

数学家业已证明，对于最困难的那一类NP问题，如果你能找到一条解决其中一个问题的捷径，那你就能解决所有的NP问题。如果这样，NP问题就变成了P问题。但问题是这样的捷径是否存在：是否P=NP。科学家猜想不存在这样的捷径：但如何证明这一点是数学领域中最大的悬而未决的问题之一。

19世纪40年代，贝尔实验室的科学家克劳德.香农(Claude Shannon)证明：比特（bits)的概念不仅仅是用于计算机，它们是信息从一个系统传递到另一个系统的基本单元。一个比特可以用多快的速度从甲处传递到乙处；对于给定的信息通道，可以有多少信息来回传递；从内存中抹去一位字节需要多少能量，这些问题都可以通过一系列物理定律（香农信息定律）得出。所有的传统信息处理器都遵守香农信息定律---而在我们的脑海里翻转的似乎就是信息：那信息定律是否意味着我们的思维可以简约成一系列的比特和字节？我们是否也仅仅就是台计算机呢？这个问题现在还没有得到回答。

但有一个领域用传统计算机（信息论）不能完全表述：量子理论。量子理论的不确定性使得原子或其他量子实体可以存储的信息状态，不局限于信息理论中的“要么0，要么1”的状态，而可以同时是“0态”或“1态”。在世界各地的物理学家正在建造原始的量子计算机，通过利用这个以及其他的量子效应去做普通计算机证明无法办到的事：譬如通过区区几条查询（比常规方法少得多），在一个数据库里找到特定的纪录项。不过，科学家仍在研究是什么量子机制使量子计算机如此功能强大，以及如何制造可以投入实用的量子计算机。

通过了解量子世界的奇异逻辑，并把它用于计算，科学家可以深入了解亚原子世界的法则。对计算能力的追求看似平凡，但也许就是类似的问题可以带来对量子领域的全新理解。

元宝推荐：ArKrXe,

本帖一共被 4 帖引用 (帖内工具实现)

复【25个科学问题征文】常规计算的极限是什么？

家园

这个题目本来是MacArthur兄先定下的。

我在看的时候很感兴趣，忍不住翻译起来。

盼着与河里的高人探讨，且不知MacArthur兄进展如何，就抢发在这里，向MacArthur兄道歉。

这篇文章很浅显，作者似乎主题并不集中，已开始偏向数学方面，后来又介绍量子计算机。

我对量子计算机不甚了解，那位高人可以详细介绍？

关于计算问题，我实际上对基因算法更感兴趣。因为它处理的是常规推导算法无法覆盖的解题空间，其思维方式也不是遵循传统的化复杂问题为简单问题的分解路径，是一个有趣的发展方向。不知河里有没有这方面的专业人士，以及象我这样的爱好者？

复这个题目本来是MacArthur兄先定下的。