📄 texta-24.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" link="#0000FF" vlink="#3399FF" alink="#FF0066">
<div id="Layer1" style="position:absolute; width:711px; height:21px; z-index:1; top: 10px; background-color: #CCCCCC; layer-background-color: #CCCCCC; border: 1px none #000000; left: 26px"><b>|</b><font face="宋体" size="2"><a href="../text1/text1-0.htm">第一章</a></font><b>|</b><font face="宋体" size="2"><a href="../text2/text2-0.htm">第二章</a></font><b>|</b><font face="宋体" size="2"><a href="../text3/text3-0.htm">第三章</a></font><b>|</b><font face="宋体" size="2"><a href="../text4/text4-0.htm">第四章</a></font><b>|</b><font face="宋体" size="2"><a href="../text5/text5-0.htm">第五章</a></font><b>|</b><font face="宋体" size="2"><a href="../text6/text6-0.htm">第六章</a></font><b>|</b><font face="宋体" size="2"><a href="../text7/text7-0.htm">第七章</a></font><b>|</b><font face="宋体" size="2"><a href="../text8/text8-0.htm">第八章</a></font><b>|</b><font face="宋体" size="2"><a href="../text9/text9-0.htm">第九章</a></font><b>|</b><font face="宋体" size="2"><a href="../text10/text10-0.htm">第十章</a></font><b>|</b><font size="2" face="宋体">算法分析<b><font color="#000000">|</font></b>
</font></div>
<pre align="left"><b><font face="宋体" size="4" color="#000000">
<font color="#FF0000">图灵机的计算步骤</font>
----根据有限控制器的当前状态以及每个磁头注视的带符号执行以下
操作。
<i><font color="#0033CC" face="Arial, Helvetica, sans-serif">1.</font></i> <i><font color="#0033CC" face="Arial, Helvetica, sans-serif">改变有限控制状态。
2. 在某几个或全部磁头所指的单元内，擦去当前的带符号，印上新
的带符号。
3. 任几个或全部磁头不相关地向左移动一格（L）或向右移动
一格（R）或保持不动（S）。
</font></i>
可以用七元组 <i><font color="#0033CC" face="Arial, Helvetica, sans-serif"> <font color="#FF0000"> （Q, T, I, </font></font></i><font color="#FF0000"><i><font face="Arial, Helvetica, sans-serif">δ</font></i></font><i><font color="#0033CC" face="Arial, Helvetica, sans-serif"><font color="#FF0000">, b, qo, qf） </font></font></i>形式地表示图灵机
其中
1. Q是状态的有限集合；
2. T是带符号的有限集合；
3. I是输入符号的集合，I<img src="image/belong0.gif" width="15" height="16">T;
4. δ<font color="#FF0000"><i></i></font> 转移函数
5. b 是空白符，b∈T - I;
6. qo是初始状态；
7. qf 是最后（接受）状态；
<font size="2"> </font>
</font></b><font face="宋体" size="4" color="#000000"><font color="#FF0000"><i><font face="Arial, Helvetica, sans-serif" color="#000000">δ</font></i></font></font><b><font face="宋体" size="4" color="#000000"> 转移函数---是 <font color="#0033CC"><i><font face="Arial, Helvetica, sans-serif">Q×Tk</font></i></font> 的子集到 <i><font color="#0033CC" face="Arial, Helvetica, sans-serif">Q ×( T × {L, R, S})</font></i><img src="image/k.gif" width="11" height="11" vspace="10"> 的一个单值映
射。即对于由一个状态和k个带上磁头扫描着的符号组成的某个k+1元组，
它产生一个新状态和k个对偶，每一对偶含有一个新的带符号和带头的移
动方向。
假设<font color="#FF0000"><i><font face="Arial, Helvetica, sans-serif">δ（q,a1,a2,..ak）</font></i></font><font face="Arial, Helvetica, sans-serif"><i><font color="#FF0000">=(q',(a'1,d1),(a'2,d2),…,(a'k,dk))</font></i></font>,则当图灵机
处于状态q，第i个磁头扫描着符号ai(1≤i≤k)时，移动后图灵机就进
入状态q'，把符号ai 改为a'i ，并按方向di来移动第i个磁头
(1≤i≤k)。由于Q和T的有限性，保证了函数的定义域和值域的有限性。
它们构成一台图灵机的指令表。
<font color="#FF0000">确定图灵机</font><font face="Arial, Helvetica, sans-serif" size="3" color="#CC0099"><i>（deterministic Turing machine简称DTM）</i></font>
-----δ是单值映射的图灵机
<font color="#0033CC">如果</font>
图灵机的一个输入串是输入符号集I中的字符的有穷序列，且
一个输入符号串是可接受的（即从指定的初始状态开始， 且
所有带的磁头都处于带的最左端单元上）
<font color="#0033CC">那么</font>
图灵机在一系列的转移后最终都能进入接受状态（称为正常停机）。
</font></b></pre>
<table width="732" cellspacing="0" cellpadding="0">
<tr>
<td width="327"> </td>
<td width="271"><a href="../index.htm"><img width="60" height="25" usemap="#MapMap4" border="0" src="../../images/home.gif"></a><a href="../index.htm"><map name="MapMap4"><area shape="rect" coords="42,-34,88,-15" href="text0.htm"><area shape="rect" coords="4,4,55,23" href="textA-index.htm"></map></a></td>
<td width="132"><font face="楷体_GB2312" size="2"><b> <a href="texta-23.htm">上一页</a>
<a href="textA-25.htm">下一页</a> </b></font></td>
</tr>
</table>
<pre align="left"><b><font face="宋体" size="4" color="#000000">
</font></b>
</pre>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -