可计算问题 若某问题,若存在一个 Turing机,对于 相应的初始状态, Turing机经过有限步 最终停机。称该问题是( Turing)可 计算的。 对于可计算的问题,计算复杂性的定义: 计算所需的步数或指令条数这叫时间复 杂度) ■计算所需的存储单元数量(这叫空间复杂 度)27 可计算问题 􀂄 若某问题，若存在一个Turing机，对于 相应的初始状态，Turing机经过有限步 最终停机。称该问题是（ Turing ）可 计算的。 对于可计算的问题，计算复杂性的定义： ◼计算所需的步数或指令条数(这叫时间复 杂度)。 ◼计算所需的存储单元数量(这叫空间复杂 度)