Bre*_*ren 7 theory computer-science turing-machines computation-theory formal-languages
我想知道递归和递归可枚举语言之间的区别在于停止和图灵机.我知道递归可枚举语言是递归语言的一个子集,但我不确定除此之外的差异.
你具有的关系- [R和RE向后:- [R是的(适当的)子集RE.基本上,递归语言是一个总决策者.
回想一下递归可枚举语言的定义,作为存在部分决策者的语言; 也就是说,一个图灵机,作为输入在你的字母表上输入一个单词,将根据你的语言正确地接受/拒绝这个单词,或者如果这个单词不是你的语言,它可能永远循环.
相反,递归语言是存在总决策的语言,即永不循环的语言,并且总是停止在接受或拒绝状态.
将这两个定义放在一起,很明显递归语言也是递归可枚举的,因为总决策器也是部分的(它永远不会"选择"循环而不是用正确的答案停止).
主要区别在于，在递归可枚举语言中，机器对于语言 L 中的输入字符串会停止。但对于不是 L 中的输入字符串，机器可能会停止，也可能不会停止。
当我们谈到递归语言时，无论机器是否接受它，它总是停止。如果它接受，它就会到达 (q Accept) 并停止。如果机器不接受，它会直接到达（q 停止）。
| 归档时间： |
|
| 查看次数： |
13426 次 |
| 最近记录： |