Search code examples
decidable

Undecidable if TM overwrites its input?

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?

Solution

  • PROOF:

    Build a machine B that takes as input a machine A, and simulates it without disturbing the input string (the string describing A). This is not difficult.

    Now build machine C, a modified version of B. If A ever halts, C will overwrite the input string; until then it will leave the input string untouched.

    In order to decide whether C (acting on A) ever overwrites its input string, one must decide whether A ever halts. But "does A halt" is undecidable, therefore so is "does C overwrite its input".

    INTUITION:

    With Turing machines, almost anything that isn't easy is impossible.