以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 理论计算机科学 』  (http://bbs.xml.org.cn/list.asp?boardid=64)
----  [求助]为什么描述图灵机只需要CFG就可以了？  (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=74924)

--  作者：typed_man
--  发布时间：5/19/2009 12:27:00 PM

--  [求助]为什么描述图灵机只需要CFG就可以了？
比较初级，问题是这样的：
图灵机接受的语言最高可以到达图灵可识别的，即递归可枚举语言，但为什么描述一个图灵机或者说编码一个图灵机只需要上下文无关文法就够了？这是不是因为自动机本身就只需要这个级别就完全可以描述？或者可以从其它计算模型的角度给解释一下？
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 30.273ms