文章目录
一、图灵机示例
二、图灵机示例 2
一、图灵机示例
----
指令
\rm L : (p,1) \to (q, 0, L)
初始状态下 , 状态是
\rm p
读取头 指向的字符是...向右无限延长的带子 , 带子有一个左端点 ;
当读写头当前已经指向左端点时 , 如果再向左移动 , 此时默认不进行移动 ;
二、图灵机示例 2
----
任务 : 设计一个图灵机 , 给定输入之后 ,..., 没有找到
1
, 只找到了空白字符 , 将该空白字符改为
1
, 然后向左移动一格 , 然后停下来 ;
( 自动机停下的前提是处于可接受状态 )
根据上述算法 , 构造图灵机 ;
图灵机设计..., 最关键的部分是三条指令 ;
图灵机处于开始状态
\rm q
, 读头指向
0
字符 , 左端的
0 0
是输入字符 , 查看图灵机是否接受
0 0
字符串 ;
下面图灵机后续都是...与 自动机 接受的条件是不同的 ;
图灵机计算过程中 , 一旦到达接受状态 , 立刻停机 , 不再继续进行计算 ; 并且称该图灵机是可接受的 ;
自动机即使到达接受状态 , 也要把自动机读取的字符读取完毕