图灵停机问题的一个简单论述

图灵停机问题问的是“能否设计一个算法,在判定任意的一段算法对给定的一些输入在有限步骤后停止运算时,返回是,而在判定任意的一段算法对给定的另外一些输入无法在有限步骤后停止运算时,返回否“。图灵的回答是这样的算法无法被设计出来。 问题中所谓的算法等价于图灵机。 假设存在算法A,具备这样的能力。设想对任意 … 继续阅读图灵停机问题的一个简单论述