以下语言可以决定吗？ l = {＆lt; m＆gt; ：m（x）是一台图灵机，运行时间由100 | x |^2＆＃x2b; 200}
l = {＆lt; m＆gt; ：m（x）是一台图灵机，运行时间为100 | x |^2 + 200}
我认为L是不可决定的，但我无法解决。请帮助我证明这一点。谢谢！
L = {<M> : M(x) is a Turing machine with running time bounded by 100|x|^2 + 200}
I think L is undecidable but I can't solve that. Please help me prove it. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
语言L是可判定的，因为它的性质与图灵机的结构有关。换句话说，它不满足赖斯定理的第三个条件，即不可判定的属性必须与图灵机的语言有关，而不是与机器的结构有关。
The language L is decidable because it's property is related to the structure of the turing machine. In other words, it doesn't satisfy the third condition of the Rice's theorem which states that an undecidable property must be related to the language of the turing machine and not the structure of the machine.