我试图减少停止问题以显示另一个问题是不可判定的。问题涉及一个程序,如果机器 $ m $ 写入任意存储量,则为任意存储量,并且如果它写入有限量的存储器单元。我现在正在思考,写入等于停止的有限量的内存单元,或者可以有机器在没有停止而不停止的有限量的存储单元中写入的情况下的情况下?

提前谢谢!

有帮助吗?

解决方案

考虑一台反复移动头部的图灵机,然后左,然后右侧,然后左转,等等。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top