严谨的证明的话,可以使用「形式语言」(Formal language)来证明: 在可计算理论和计算复杂度理论中,每个「计算问题」都被描述为一个一个「形式语言」,即字符串的集合。比如对于判断一个图是否是无向连通图这个问题:我们可以写为一个描述所有无向连通图的集合: 由于图灵机只能…
评论