图灵停机问题的两种符号表述

年中在读《量子计算与量子信息原理》的时候,写了一篇《图灵停机问题的一个简单论述》的阅读笔记,对大学时没学明白的图灵停机问题有了一些基本认识。今天在读《复杂》的时候,里面采用了另外一种等价的说法,在符号形式上看起来略有差异,如今记录一下加深印象。回顾量子一书中的描述,先假设存在算法A具有判定任意算法是否能够停止运算的能力,用符号表述也就是对于算法T输入mh,可以停止运算时,A回答是A(T(mh))= … 继续阅读