I came across a statement postulating that it's undecidable whether a TM overwrites any of its own input.
What would be intuition as well as an actual proof for that?
I came across a statement postulating that it's undecidable whether a TM overwrites any of its own input.
What would be intuition as well as an actual proof for that?
PROOF:
Build a machine
Bthat takes as input a machineA, and simulates it without disturbing the input string (the string describingA). This is not difficult.Now build machine
C, a modified version ofB. IfAever halts,Cwill overwrite the input string; until then it will leave the input string untouched.In order to decide whether
C(acting onA) ever overwrites its input string, one must decide whetherAever halts. But "doesAhalt" is undecidable, therefore so is "doesCoverwrite its input".INTUITION:
With Turing machines, almost anything that isn't easy is impossible.