planeheart的头脑风暴
注册日期:
2013-09-16 15:53:09
上次登录:
2016-05-11 02:38:27
邮件地址:
saintpal@163.com
兴趣领域:
数学,物理,人工生命,系统科学,计算机科学
  
可逆计算简介(摘)
2014-10-06 09:23:06  科普 

Rolf Landauer的工作表明:事实与Von Neumann,Gabor和Brillouin等优秀学者的直觉并不相符:只有将信息摧毁的运算会伴随着耗散,以Landauer命名的原理量化了信息擦除和熵增之间的联系,换言之:只有逻辑不可逆的操作必须以热力学意义上的不可逆过程执行。Landauer指出:可用添加保存计算历史的流程等方式杜绝消灭信息的不可逆操作,将计算改为可逆,从而可能实现最大限度的计算节能(至多节约到0)。Landauer本人猜测:可逆计算将会受到比普通的计算更加严重的限制:一者是可能无法执行所有可能的计算(如果不存在图灵完备的可逆模型),一者是保存计算历史会导致垃圾信息在内存中积累,从而给整体计算添加一个随着问题规模指数飙升的空间复杂度的负担。这两点(尤其是后者)会导致可逆计算无法进行复杂的工作。

Charles Bennett进一步发展了可逆计算的理论,证明了Landauer的限制完全是多余的——不耗能的可逆计算能力几乎一点都不弱于传统的计算!通过名为Lecarf-Bennett反演的技巧,一台可逆通用机可以完全模拟任意的图灵机,并且每一步都能自行将计算历史可逆地消除,至多以计算时间4倍为代价。当然,只将经典计算可逆化是不足以保证计算不耗能的,逻辑可逆仅仅是一个必要条件。Edward Fredkin 和Tommaso Toffoli的撞球计算机可以看做是一个比较直观的可逆计算理想模型,它演示了从底层直接进行无耗散的经典计算是可以符合物理直觉的。


图1 Lecarf-Bennett反演通过进行正逆两重计算的途径,巧妙摆脱了计算历史积累的负担

与经典逻辑门不同,所有的量子逻辑门都是天然可逆的(它们本质上都是幺正变换)。因此,通用量子计算本身就是对可逆计算的一个支持。在某种意义上说:找到一组恰好能做通用计算的简单量子门比对应的经典情形要容易得多,但是用它们逼近一个任意的幺正变换的复杂度很可能是惊人的。一方面:至今为止我们还没有足够有效的量子计算设备。另一方面:我不认为量子计算对解释人类意识活动有额外帮助,目前的研究证据表明人脑处理信息的方式是经典的。因此关于量子计算将不在这里进行更多讨论。

图2 麻省理工大学的Josie Ammer, Nicole Love, Scott Rixner和Carlin Vieri等人设计的第一代可逆芯片,它们确实显示出低功耗的特征。

2014-10-10 20:58:19
   plane兄发新帖了,mark之。(之前有几篇强文还没补完啊,观众强烈要求催更)。
以及,图挂了,看不到。

最近在想,计算机真是个神奇的东西。如果从传统的物理角度看一台计算机,就是一团物质而已。但似乎计算机本身在物质基础上构建了新的次元。而这个构建,基础就是逻辑门。是不是可以说,有逻辑门的地方,就潜藏着意识次元。
2014-10-11 14:02:35
   @华尔兹的哀
为啥我这边图好好的==不过那个也可以搜到
我倒是有个奇怪的想法:意识会不会依赖于不可逆的计算模型?因为我觉得如果可逆计算机上面能运行某种自主意识的智能程序,它的感觉想必是很奇怪的。
登录后才可以评论,马上登录