可逆编程语言相关理论及实践研究
作者：卫丽华
来源：《软件导刊》2015年第02期
        摘要：从编程语言的角度研究了可逆计算。首先，给出可逆编程语言流程图的3种基本结构，从而构建一个可逆编程语言的可视模型；其次，证明可逆语言的可逆图灵机完备性，进而论证其与传统编程语言在计算能力上的一致性；最后，介绍了可逆编程语言Janus并进行了编程实践。
        关键词关键词：可逆计算；可逆编程语言；流程图；图灵机；图灵完备
        DOIDOI：10.11907/rjdk.1431017
        中图分类号：TP314
        文献标识码：A文章编号文章
        编号：16727800（2015）002006204
        基金项目基金项目：南通理工学院校级科研项目（2014002）
        作者简介作者简介：卫丽华（1984-），女，江苏南通人，硕士，南通理工学院软件工程系讲师，研究方向为可逆计算。
        0引言
        可逆计算作为一个新兴学科，对未来计算机的持续发展起着决定性的作用。自20世纪60年代以来，计算机硬件一直遵循着Moore定律＼[1＼]高速发展，但这种发展趋势预计会在2020年左右终结＼[2＼]，主要原因如下：单位面积器件数量的增加，会导致产生的热量超出芯片能承受的极限。R·landauer最早考虑了能耗导致计算机芯片发热的问题＼[3＼]，他指出能耗来源于计算过程中的不可逆操作，因此采用可逆计算可以大大降低计算机的能耗。可逆计算主要关注两个方面：物理可逆和逻辑可逆，R.Landauer在文献＼[3＼]中证明，如果一个计算过程物理可逆，那么该过程须同时逻辑可逆。一个计算过程如果不仅能从输入状态得到输出状态（正向），并且能从输出状态唯一确定输入状态（反向），那么该计算过程便是逻辑可逆的。
        当今流行的计算机（RAM机或图灵机）都是逻辑不可逆的，因为它们在计算过程中会销毁或丢失信息，从而不能回推前状态。Landauer认为通过保存运算过程中的历史信息，可以将不可逆性通过逆向跟踪程序流程图得到。本文根据传统程序流程图的3种基本结构，将一个不可逆运算转变成可逆运算，引入额外信息通过反向运算清除＼[4＼]。理论上讲，只要存储空间足够，任何不可逆计算都可以转换成可逆计算。目前已经出现了一些可逆计算模型，比如可逆图灵机＼目前流行的编程语言[4＼]和可逆细胞自动机＼[5＼]，但针对较高逻辑层级的软件（即编程语言）进行的研究还比较欠缺。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。