佚名

计算和信息

计算、信息

  • 计算需要时间，信息需要空间。因此，计算、信息和时空有关
    • 计算——信息
    • CPU——内存
    • 处理器——存储器
    • 算力——数据
    • 算法——数据结构
    • 时间复杂度——空间复杂度
  • 计算的粒度
    • 经典力学——算盘、算珠、机械计算机、齿轮
    • 电动力学——开关电路、继电器
    • 量子力学——数字电子计算机、晶体管、量子计算机、光子
    • 粒子物理——？
  • 计算的本质是利用物理规律，进行信息处理。计算的粒度越小，计算的速度越快
    • 计算既受到数学的限制（比如可计算性），也受到物理的限制（比如物理定律）
    • 尽管我们可以考虑所有实数，然而从物理实现的视角出发，可计算的实数是有限的。因此，所有实数本身是形式化的，并非所有数学都有对应的物理实现；在这一意义下，数学位于形式空间，物理位于实现空间
    • 数学问题的困难程度可以表现为大数（Big Number）的计算。如果我们可以计算充分大的实数，那么我们可以解决充分困难的数学问题。比如，对于忙碌海狸数（Busy Beaver）BB(n)
      • Riemann假设对应于BB(744)
      • Goldbach猜想对应于BB(27)
      • 最近，利用Coq证明助手，我们可以形式化地证明

            \[ BB(5) = 47176870. \]

量子计算

  • Scott Aaronson是一位忙碌海狸数和量子计算的研究者。他的博客上方有一句话——If you take nothing else from this blog: quantum computers won’t solve hard problems instantly by just trying all solutions in parallel.——因此，计算的困难是本质性的