科学网 › 标签 › 状态转移函数

标签: 状态转移函数

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

图灵机状态转移函数为什么是部分函数？: 热度 1 accsys 2014-11-8 15:11; 图灵机状态转移函数为什么是部分函数？姜咏江图灵机是神秘的机器，能够很通俗地将它解释清楚文章很难找到。为了透彻地理解图灵，我们不妨先对图灵机定义做一点详细的研究。 1.1.1. 图灵机的数学定义关于图灵机的数学定义一般介绍如下：一台图灵机M是一个七元组，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中 Q，Σ，Γ 都是有限集合，且满足：（1）Q 是有限状态集合；（2）Σ是输入字母表，其中不包含特殊的空白符 □；（3）Γ 是带子上字母表，其中 □∈Γ且 Σ Γ ；（4）δ：Q×Γ→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移；（5）q0∈Q是起始状态；（6）qaccept是接受状态；（7）qreject是拒绝接收状态，且qreject≠qaccept。这是啥意思？定义的（2）和（3）条比较好理解，Σ可以理解成英文的字母符号表，最简单的可以将它理解成Σ=｛0,1｝。Γ是写在带子上的字母表，为了区分不同的连续表达的意思，用空格来区分这是书写的常规。这里说 Σ Γ 是因为集合Γ比集合Σ多了一个空格字符□。我们用最简单的情况考虑，理解Γ=｛0,1,□｝。用一定位数的二进制数可以表达语言文字。例如，8位的西文ascll编码表，或者16位的unicode编码表。16位的汉字编码表等。将Γ带子上的“格子”是理解成单独的0和1，还是理解成由一定位数的二进制编码组织的数据？这是理解好图灵机的一个关键问题。笔者认为，将带子上的格子理解成能写入固定位数的二进制数较妥。定义中的（5）是任何机器运行所必需的条件。q0∈Q是说q0也是一个状态，但究竟是怎样的一种状态？却是留下了进一步想象的空间。定义（6）和（7）的理解是多样的。接受状态和拒绝状态是指什么？是指转移函数接受读写头读出的字符还是拒绝？定义中最难理解的是δ：Q×Γ→Q×Γ×{L,R}这个转移函数。关于转移函数的讨论，我们用具体的问题来看一下。表 1是我们设计的一个二进制两位数乘法运算的图灵机转移函数。Σ＝｛00，01，10，11｝。不考虑空格和怎样打印输出，实际这个转移函数就是δ：Q×Σ→Q×Σ。左面Σ是读入的二进制数，右面的Σ应该是输出两位的二进制数。从表 1的实际乘法运算，我们看到好几项乘法的结果都不在Σ中，此时图灵机就不能够识别，因而会产生拒绝的情况，造成停机。本来两位二进制数乘积应是｛00，01，10，11，100，110，1001｝这是两位数的乘法运算值域，但Σ中不包含100、110、1001，也就是说函数不构成满射，所以才叫部分函数。表中能够返回 q 0 的情况就叫接受状态 qaccept 。 Q={q 0 ,q 1 ,q 2 ,q 3 ,q 4 ,qaccept,} 。定义中的 qreject 实际上应不属于 Q ，不然就造成了悖论。表 1 两位数乘法运算图灵机转移函数序号前状态Q 输入乘法结果后状态Q 1 q 0 00 q 1 2 01 q 2 3 10 q 3 4 11 q 4 5 q 1 00 00 qaccept 6 01 00 qaccept 7 10 00 qaccept 8 11 00 qaccept 9 q 2 00 00 qaccept 10 01 01 qaccept 11 10 10 qaccept 12 11 11 qaccept 13 q 3 00 00 qaccept 14 01 10 qaccept 15 10 100 qreject 16 11 110 qreject 17 q 4 00 00 qaccept 18 01 11 qaccept 18 10 110 qreject 20 11 1001 qreject 2014-11-8; 个人分类: 科研讨论|8775 次阅读|1 个评论

一个能够让你明白图灵机的例子: 热度 2 accsys 2014-11-3 14:58; 一个能够让你明白图灵机的例子姜咏江读了图灵的文章，根据我的理解，设计个逻辑运算的例子：设 M= （ Q ，Σ，Γ，δ， q0,qaccept,qreject ）其中Σ＝｛ 0 ， 1 ， + ， * ，！｝， Γ＝｛ □ ， 0 ， 1 ， + ， * ，！｝。Γ的书写格式为“！ x ”“ +xy ”“ *xy ”并要以“ □□□□ ”间隔。表格中的 L 、 R 表示读写头左移一格或右移一格。每个字符占用一格。运算结束以后再读入一个空格，让读写头晃一下，再进入开始状态做下面的运算。从表 2‑1 我们可以看到，在此表中图灵机的状态集合 Q={ x,y,z,z0,z1,f,f0,f1,end,erro } ，其中 x 是初始状态， end 是运算结束状态， erro 是停机拒绝状态。表中 symbol 是读写头每次读入的内容，它与 m-config 一起构成了定义域元素，而经过操作行为 Behaviour ，其中包括移动读写头和输出（打印）数据，而转化为最终状态 Final m-config 。这一前一后的状态转换，形成了有序的运算操作，最终在不出现错误的情况下，得到运算的结果。注意， operations 一栏 p0 ， p1 ， p* 分别表示读写头往当前格子上写 0 、 1 和 * 字符，移动 R 或 L 与它们排在一起，表明了动作同时，也标明了先后顺序。表 2 ‑ 1 图灵机状态变化表 Configuration Behaviour 解释 m-config. symbol operations Final m-config. x □ R x x=q0 。 x 是接受开始状态。 ! R y * R z + 0 1 R R,P*,R,P*,R R,P*,R,P*,R f erro erro Y （逻辑非） □ R,P*,R,P*,R erro Erro 是拒绝状态 0 R,p1 end 接受 1 R,p0 end ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R erro + R,P*,R,P*,R erro Z （逻辑与） □ R,P*,R,P*,R erro 0 R Z0 接受 1 R Z1 ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R erro + R,P*,R,P*,R erro Z0 （逻辑与） □ ,P*,R,P*,R erro 0 R, p0 end 接受 1 R,p0 end ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R Erro + R,P*,R,P*,R Erro Z1 （逻辑与） □ R,P*,R,P*,R erro 0 R, p0 end 接受 1 R,p1 end ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R Erro + R,P*,R,P*,R Erro f （逻辑或） □ R,P*,R,P*,R erro 0 R f0 接受 1 R f1 ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R Erro + R,P*,R,P*,R Erro f0 （逻辑或） □ R,P*,R,P*,R erro 0 R, p0 end 接受 1 R,p1 end ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R Erro + R,P*,R,P*,R Erro f1 （逻辑或） □ R,P*,R,P*,R erro 0 R,P1 end 接受 1 R,P1 end ! R,P*,R,P*,R erro 拒绝 * R,P*,R,P*,R erro + R,P*,R,P*,R erro end （正常结束） □ R,L,R x 让读写头晃动表达继续逻辑运算 0 erro 拒绝 1 erro ! erro * erro + erro erro Any way qreject 停机从从表 2‑1 我们不难看出，影响下一个状态出现的每一个过程都与原来的状态 Q （ m-config ）和输入数据 Symbol （属于集合 Γ中元素）有关。经过 operations 操作，才到达了新的状态 Q' （ Final m-config ）。显然这种确定的映射可以用 Q'= δ (q, γ ）来表示， q∈ Q ， γ∈ Γ。表 2‑1 就是具体的映射 Q'= δ (q, γ ）。图灵机的 qaccept 在这个例子中就是 end ，而 qrejet 就是 erro 。特别要说明，当我们将 Q 、Σ和Γ中的元素也都用二进制数表示的时候， Q'= δ ( q, γ ）就是函数。下面添加详细的解释。例如，我们要计算逻辑值 1 和 0 的与运算和或运算结果。先可以在带子上安格写入： □□□□*10 □□□□ +10□□□□ 这里要用 4 个空格区分两组运算，这是设计的规定。初始化时读写头定在最左边的位置。开始状态是 x ，与读写头读入的一个空格“ □ ” 组成一组“ x 和 □ ”，向右在 operations 栏有 R ，这是让读写头右移一格后，进入了下一个状态，从表上看，这种情况的下一个状态仍然是 x 。这样连续进行 4 步，在第 5 步，读写头将读到“ * ”，根据表中“ x 和 * ”状态的规定，现将读写头右移，并决定出状态“ z ”。第 6 步要到左边状态栏找到“ z ”，这时读写头会读出“ 1 ”。依据“ z 和 1 ”向右见到“ R ”，这是将读写头右移一位的控制，并在下一个状态栏找到状态 z1 。回头再到左边栏找到“ z1 ”，这时读写头将读到“ 0 ”。第 7 步，要依据“ z1 和 0 ”一行的操作“ R ， P0 ”现将读写头右移一位，然后在空格位置写上“ 0 ”，并进入到“ end ”状态。第 8 步，左面的“ end ”状态若有读写头读进空格，则依“ end 和 □ ”行，见操作项是“ R,L,R ”，这是晃动读写头，表示运算结束，前面写出的“ 0 ”就是 1 和 0 做与运算的结果。如果读写头读入的是错误的数据，会连续打印出2个星号“**”表明带子上的输入有误，那么就会进入“ erro ”状态，拒绝继续执行，同时停机。不是错误的情况，仍然可以让读写头继续读。因为得出结果之后由“ end 和 □ ”状态确定的下一个状态是 x ，因而又回到了开始运行的情况。连续地 3 次读到空格后，就可以读到“ + ”，按着与运算的查找方法，就可以最后得出 1 和 0 做或运算的结果了。 2014－11－3; 个人分类: 计算机核|51540 次阅读|3 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 状态转移函数

相关帖子

相关日志

关闭安全验证