{<M> =M是接受3字}({L(M)|=3)的TM
{<M> =M是接受3字}({L(M)|=3)的TM
提问于 2016-06-16 14:04:25
我被这个问题困住了
{ that是一个接受三个字的TM }
我知道如何解决|L(M)|>3或|L(M)|<3，但是当涉及到|L(M)|=3时，我不知道如何继续！
回答 2
Stack Overflow用户
发布于 2016-06-17 07:45:42
用L(M)|=3这一事实是否意味着l(M)的|>2和L(M)的|<4，或者用L(M)|=3和L(M)|>3来决定L(M)|>2，这些都是用你说的你知道怎么做的东西。
当然，如果允许你使用Willem提到的Rice定理，那么答案是非常直接的。
Stack Overflow用户
发布于 2021-01-12 04:12:58
根据车削机的非单调性，利用Rice定理。让我们以一个例子为例:我们可以说(一种被旋转机器接受的语言) T{yes}={0,10,11}和(一种不被机器接受的语言) T{no}={0,10,11,1}，所以这里Tyes是Tno的一个适当子集。因此，这个问题是无法决定的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37861549
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号