空间、旅店、无穷、图灵、量子

假设有一个拥有可数无穷多个房间的旅馆，且所有的房间均已客满。或许有人会认为此时这一旅馆将无法再接纳新的客人（如同有限个房间的情况），但事实上并非如此

设想此时有一个客人想要入住该旅馆。由于旅馆拥有无穷个房间，因而我们可以将原先在1号房间原有的客人安置到2号房间、2号房间原有的客人安置到3号房间，以此类推，这样就空出了1号房间留给新的客人。重复这一过程，我们就能够使任意有限个客人入住到旅馆内

无穷个新客人

另外，我们还能使可数无穷个新客人住到旅馆中：将1号房间原有的客人安置到2号房间、2号房间原有的客人安置到4号房间、n号房间原有的客人安置到2n号房间，这样所有的奇数房间就都能够空出来以容纳新的客人

无穷个客车且每个客车有无穷客人

我们甚至能够将可数无限个客车上的人（其中每个客车上有可数无限个客人）安排进旅馆。不过，这需要有一个前提条件：所有客车上的每个座位都已经编好了次序（即旅馆管理员对客人的安排满足选择公理）。首先，如同前面一样将所有奇数房间都清空，再将第一辆客车上的客人安排在第3*2^n号房间（n=1， 2， 3，...）、第二辆客车上的客人安排在第5*2^n号房间（n=1， 2， 3，...），以此类推，将第i辆客车上的客人安排在第p*2^n号房间（其中，p是第i+1个质数）。

另外，还能够通过客车的车牌号与客人的座位号来解决这一问题。先将旅馆设为第0号客车，然后将车牌号与座位号交替书写，即能得到客人的房间号码。如果客人是在1729号房间则移动到01070209号房间，如果客人是在198号客车上的4935座则移到第4199385号房间。

无穷+1等于无穷；无穷+N等于无穷，无穷加无穷，无穷乘无穷，那还是无穷，无穷是纹丝不动的，又是随时变化的，无穷是可以包含若干个无穷的

任何有限的数字，在无穷面前，毫无意义

那是因为，你不懂无穷，无穷就是无穷，0.99999...后面，即便跟葛立恒数的阶乘那么多的9，都依然不是1，但是跟了无穷，就是1。这就是无穷

听上去，希尔伯特旅馆悖论好像没啥用。其实不然，人类在很多领域几乎都必然面对“无穷”这个问题，至少在理论推导和概念验证环节，面对无穷几乎是必然的。一个事物可以比另一个更无穷，但它们俩都还是无穷。这样的思路可以进行很多假设，也可以解释很多问题

康托尔给集合下的定义：

1.我们将由一个或多个确定的个体（元素）构成的整体叫做集合A，集合中元素的个数叫做势|A|。如，{0，1，2，3，4 }表示一个集合-记为A，它的元素个数为｜A｜=5.

2.如何定义“一样多”。康托尔的想法是两个集合间的元素能“一一对应”。如，集合B=｛a，b，c，d，e｝，|B|=5，有|A|=|B|.它们”一样多”.同时，我们注意到:0→a， 1→b，2→c，3→d，4→e.两个集合A与B能够“一一对应”

再来看看正整数与有理数的对应

按照箭头的方向，我们得到一个与自然数”一一对应”的结合：{1，2，1/2，1/3，3，4，3/2，…..}.所以正整数与有理数是一样多的，或者“势”一样。但实数的全体与正整数的全体却是不能构成这样的“一一对应”的。康托尔使用了反证法。

假设实数的全体（先取0到1之间的所有实数）可以与正整数“一一对应”，按照上图将其罗列出来。现在我们构造一个数：它的第一位小数不为a1（用！a1表示），第二位小数不为a2，……依次下去，我们发现，得到的数0.！a1!a2….不是列举中的任何一个数。换句话说，我们假设（0，1）之间的数列举完了，结果又出现了一个新的实数。矛盾。这样康托尔得到(0，1)之间的实数比正整数要“多”，进而得到实数的个数比正整数要“多”.

在康托尔的理论里，所有自然数、实数等都能构成集合，也就是自然数集、实数集等是实际存在的，无穷也就自然的向“实无穷”倾斜了。这些理论让他的老师克罗内克接受不了，一轮轮的理论攻击

图灵机是一种假想的机器 1936年数学家艾伦·图灵，尽管它很简单，机器可以模拟任何计算机算法，无论怎样太复杂了！

; This example program checks if the input string is a binary palindrome.

; Input: a string of 0's and 1's， eg '1001001'

; Machine starts in state 0.

; State 0: read the leftmost symbol

0 0 _ r 1o

0 1 _ r 1i

0 __* accept ; Empty input

; State 1o， 1i: find the rightmost symbol

1o __ l 2o

1o ** r 1o

1i __ l 2i

1i ** r 1i

; State 2o， 2i: check if the rightmost symbol matches the most recently read left-hand symbol

2o 0 _ l 3

2o __* accept

2o *** reject

2i 1 _ l 3

2i __* accept

2i *** reject

; State 3， 4: return to left end of remaining input

3 __* accept

3 ** l 4

4 ** l 4

4 __ r 0 ; Back to the beginning

accept *: r accept2

accept2 *)* halt-accept

reject _: r reject2

reject *_ l reject

reject2 *(* halt-reject

在量子物理中，对一个系统状态的完整描述需要使用复数，即量子系统的状态是一个位于 2n维向量空间中的一个点。右括向量|x⟩意味着 x是一个(纯)量子态。与这个量子系统相关的希尔伯特空间是 2n个量子态作为基向量的复向量（complex vector space）空间，系统在任何时候的状态由这个希尔伯特空间中的一个单位长度向量表示。

同时系统的叠加态可表示为：∑i=02n−1ai|Si⟩

其中振幅（amplitudes） ai为满足Σi|ai|2=1的复数，每一个|Si⟩为希尔伯特空间中的一个基向量。

为了使用物理系统进行计算，我们必须能够改变系统的状态。量子力学定律只允许状态向量的幺正转换。一个幺正矩阵的共轭转置（conjugate transpose）等于它的逆矩阵，并且要求状态变换由酉矩阵来表示，这就保证了得到所有可能结果的概率之和为1。同时量子电路(和量子计算机)的定义只允许局部幺正转换；也就是说，对固定数目的比特进行酉（幺正）变换。

值得注意的是：量子计算机的计算能力在本质上与图灵机等价，但在计算复杂度上可以优于图灵机（如果这也算是计算能力的话。）。现实中的量子计算机的计算能力可以在多项式时间内解决 BQP，并没有想象中的那么强。

但是，尽管目前可以通过结构与算法优化使计算能力不断提高，但量子计算机的计算能力还是有真正的上限的：即布莱梅曼极限（Bremermann's limit）。在量子物理框架下，我们宇宙中所有物质的计算能力都不可能超过每千克 c2ℏ bits/s（h为普朗克常数，c为光速）这也是量子计算机真正无法逾越的计算速度极限。而且你也不可能真正地达到该极限，因为所需能量会使你的计算机直接坍塌成一个黑洞。

最后值得一提的是，只要对量子力学中算符的线性要求做些微的放宽，例如，温伯格引入的非线性算符（这些工作出现在温伯格试图研讨的所谓非线性量子力学中）得到允许，则我们可以在新型量子计算机上用多项式时间求解 PSPACE完全问题（ NP完全问题自然不在话下）。

但是：由于非线性的引入一定会同时容许超光速通信和违背热力学第二定律的结果，所以提议基本是不可行的。

集合+距离=度量空间

集合+线性=线性空间

线性空间+范数=赋范线性空间

赋范线性空间+内积=内积空间

内积空间+完备=希尔伯特空间

赋范线性空间+完备=巴拿赫空间

如果一个空间是线性的，完备的，并且规定了范数，内积和距离的，就叫做希尔伯特空间。虽然这些性质比水果的性质更难理解，但本质上都是一个推广的过程

希尔伯特空间=完备的内积空间⊂内积空间

范数运算+向量空间=(线性）赋范空间（线性）赋范空间+内积运算=内积空间

（线性）赋范空间+完备性=巴拿赫空间

内积空间+完备性+有限维=欧几里德空间

内积空间+完备性=希尔伯特空间

封闭类时曲线计算：封闭类时曲线计算机所需要的可以进行时间旅行的类时闭曲线时空的特殊时空结构在数学上是可能的。但如果在正能量条件普世的条件下现实的物理系统就不允许它的出现和存在。除非自然规律允许负能量的物质出现。

封闭类时曲线可以明确的计算能力的问题判定范围是全部 PSPACE。即使用一个 Polynomial - size字符串，封闭类时曲线计算机可以在多项式时间内准确判定全部PSPACE。但进一步放宽条件可得到一个新的计算能力范围 ComputableCTC，可以证明 ComputableCTC=Δ⁰₂。不过这不代表它真的就“一定可以解决“。因为这需要任意长度字符串的计算在封闭类时曲线中得到允许（这代表需要无限宽的输入通道）才有可能真正做到。

面对这类不可计算问题时，计算机所拥有的符合自治性结果将不再唯一；面对自治性结果不唯一的情况时，大自然将会让封闭类时曲线计算机从所有的自治性结果中选择令整体冯·诺依曼熵最大的结果。不过这是一个坏消息，因为直觉上计算机的电路板被烧穿，整个机器崩溃会带来更高的冯·诺依曼熵。当计算机对“机器崩溃，直接坏掉。“和“吐出该问题的判定结果。“的选择可能性时，封闭类时曲线计算机更有可能会选择前者......