1513图灵机 与RAM模型类似,图灵机既可作为语言接受器,也可作为 计算函数的装置。 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入 所需的最大计算步数。如果对某个长度为η的输入,图灵机不停 机,T(n)对这个n值无定义。 图灵机的空间复杂性S(n是它处理所有长度为n的输入时, 在k条带上所使用过的方格数的总和。如果某个读写头无限地向 右移动而不停机,S(n)也无定义。9 15.1.3 图灵机 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入 所需的最大计算步数。如果对某个长度为n的输入，图灵机不停 机，T(n)对这个n值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时， 在k条带上所使用过的方格数的总和。如果某个读写头无限地向 右移动而不停机，S(n)也无定义。 与RAM模型类似，图灵机既可作为语言接受器，也可作为 计算函数的装置