计算科学的新领域:DNA计算(Ⅲ)

摘要

DNA计算是应用分子生物技术进行计算的新方法.从理论上研究DNA计算方法,有利于推动理论计算科学的发展.本系列文章应用形式语言及自动机理论技术,系统地探讨了DNA分子的可计算性及其计算能力.本文主要介绍DNA剪接计算模型的文法结构和剪接计算方法,探讨了不同DNA剪接计算模型的计算能力,证明了所有图灵机可计算的函数理论上都可以通过DNA剪接计算模型来计算.