可判定语言（计算模型）

L = {< M> | M是TM和L的（M）的结合和对H_TM是在RE}

（H_TM = {< M，W> | M是上瓦特}停止一个TM）

2016-05-29 ChikChak

这个问题可能应该继续[cs.stackexchange.com]（http://cs.stackexchange.com/） – harold

我假定< ...>是Gödelization中TM的编号。 L（M）是一组词，而H_TM是一组对。因此，他们的联盟是不相交的，两者都不会出现任何因素。通常情况下，工会如果有两个部分是可以列举的。 H_TM是可枚举的，因此可枚举性仅取决于L（M）。但是作为TM的语言意味着可以明确无误地判断。因此，在定义L时M的条件总是为真，因此L是所有TM描述的集合，这是规则的且明确可判定的。

来源

2016-05-30 09:01:57

我想我的符号不清楚：基本上是一个图灵机的encoidng，所以当另一台机器得到如输入它可以模拟它。此外，H_TM是暂停问题，你说的是可以确定的，我不知道为什么。 – ChikChak

对不起！当我在L的定义中提到RE时，我写了可判断的。当然，暂停问题是不可判定的，但它是可以枚举的，我纠正了我的答案。 –

我有点困惑 - 符号L（M）是否意味着M决定L？或者它可能只识别L？ – ChikChak

可判定语言（计算模型）

回答

相关问题