表明空性和有限性对于线性有界自动机是不可解的

Question

证明线性有界自动机的空性和有限性是无解的，没看懂，谁能帮帮我？

Answer 1

解决空性意味着你可以确定线性有界自动机是否接受任何东西，解决有限性意味着你可以确定线性有界自动机是否接受有限集。

线性有界自动机的空性不可解的证明取决于它对于图灵机也是不可解的事实。

对于每个图灵机，都有一个线性有界自动机，它接受一组字符串，这些字符串是图灵机的有效停止计算。

如果图灵机什么都不接受，则有效的停止计算字符串集为空。接受此图灵机停止计算的线性有界自动机也将不接受任何内容。如果可以确定线性有界自动机是否不接受任何东西，那么就可以确定图灵机是否不接受任何东西，但这是矛盾的，因为无法判断图灵机是否不接受任何东西机器什么都不接受。

线性有界自动机有限性不可解的证明是一样的。如果图灵机接受的集合是有限的，则线性有界自动机接受该有限集合。如果可以确定线性有界自动机是否接受有限集，那么也可以确定图灵机是否接受有限集，但这是矛盾的，因为无法判断图灵机是否接受接受有限集。

这些问题对于图灵机是无法解决的，因为对于可计算集来说，只有微不足道的集合属性是可以解决的。集合 K = { i | M_i(i) halts }是无解的，有限性和空性可以归结为集合K，这就是它们对图灵机无解的原因。