Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(1)
发信站: 哈工大紫丁香 (2001年06月14日15:40:09 星期四), 站内信件


                      可计算性简明纲要
第一节 计算模型
定义 一个k带图灵机是一个6元组(Sigma, Tou, S,F,*,M),其中
Sigma是一个有限集合,称为带字符集;Tou是一个有限集合,称为
状态集;S属于Tou,称为开始状态;F是Tou的子集,称为结束状态集;
*属于Sigma,称为空字符;M是
   Sigma^k X Tou -> Sigma^k X Tou X {L,R,O}^k
的映射.图灵机简写为TM.
注解 通常把TM理解为一台具有k条无限长双向带和一个记忆状态
的内存的机器.根据在所有带上读到的字符和当前状态,决定转换
为哪个状态,在每条带上写一个什么字符,以及每个读写头的运动
(向左一格,向右一格,还是不动).
定义 一个函数是TM可计算的iff把它的输入放在TM的前k-1条带
上开始运行TM,有限步后一定会停机,并且运行结束后函数值在
第k条带上.如果不一定会停机,但停机后函数值一定在第k条带
上,则称为半可计算的.
注解 输入输出放在哪里并不重要,只要在讨论时前后一致就可以
了.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]