骤,最后得到一个满足预先规定的符号串的变换过程?图灵的研究成果是:可计算性= 图灵可计算性–任一过程是能行的(理论上的能行,能够具体表现在一个算法中),当且仅当它能够被一台图灵机实现 5 2.2 图灵机计算模型 6图灵机的特征?图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成?写在带子上的符号为一个有穷字母表: {S 0,S 1,S 2, S p}?一个给定机器的程序认为是机器内的五元组(q iS jS k Rq l或q iS jS k Lq l或q iS jS k Nq l)形式的指令集–q i表示机器目前所处的状态–S j表示机器从方格中读入的符号–S k表示机器用来代替 S j写入方格中的符号–R、L、N分别表示向右移一格、向左移一格、不移动–q l表示下一步机器的状态 7图灵机的工作原理?机器从给定带子上的某起始点出发,根据其初始状态及机内五元组决定其动作,经过有限步骤机器停止时,带子上的信息即为机器计算的结果。?可能产生的问题: –无休止工作?如: q 1S 2S 2 Rq 3指令和 q 3S 3S 3 Lq 1指令同时出现在机器中时–产生二义性?如: q 3S 2S 2 Rq 4和q 3S 2S 4 Lq 6指令同时出现在机器中时 8实例?设b表示空格, q1 表示机器的初始状态, q4 表示机器的结束状态,如果带子上的输入信息是 10100010 ,读入头对准最右边第一个为 0的方格,状态为初始状态 q1 。按照以下规则执行之后,输出正确的计算结果。 q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4 q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4 9图灵机对例子的计算过程 S(x ) = x + 1
全文预览
