decidable - 如果 TM 覆盖其输入，则无法确定？

Question

我遇到了一个声明，假设 TM 是否会覆盖它自己的任何输入是无法确定的。

什么是直觉以及对此的实际证明？

Answer 1

证明：

构建一个以 machineB为输入的机器A，并在不干扰输入字符串（描述字符串A）的情况下对其进行模拟。这并不难。

现在建机C，修改版B。如果A停止，C将覆盖输入字符串；在此之前，它将保持输入字符串不变。

为了决定C（作用于A）是否覆盖其输入字符串，必须决定是否A停止。但是“是否A停止”是无法确定的，因此“是否C覆盖其输入”也是如此。

直觉：

使用图灵机，几乎任何不容易的事情都是不可能的。