美文网首页
递归可枚举、递归

递归可枚举、递归

作者: 约翰L | 来源:发表于2018-11-30 00:34 被阅读0次

    图灵机对于任意输入,只有三种状态:

    1.接受停机。

    2.状态转移函数无定义,落空停机。

    3.一直有定义,但永不停机。

    1被称为接受,23都算不接受,但2是拒绝,3是不停机(你不能说他不接受,因为程序不终止无法判定)。

    于是针对23区别产生了,语言L任意串能实现12则称为递归语言,即任意一个元素都能判定是不是被接受,这样就被称为递归语言。

    语言L任意串能实现13则被称为递归可枚举语言,即任意一个元素如果在接受集合之内,TM一定会停机且接受,但是如果不在接受集合内,TM不会停机,即无法验证。

    这种只能验证事先知道结果的语言,称为递归可枚举语言,即可以以暴力枚举的方式判定被接受串。

    相关文章

      网友评论

          本文标题:递归可枚举、递归

          本文链接:https://www.haomeiwen.com/subject/lotccqtx.html