Answer Happy

A computer uses some fixed operating system under which all its
programs run. A “program” can be
thought of as a function that takes one string as input and
produces another string as output. On the
other hand, a program written in a specific language can be thought
of as a string itself. (For example,
it can be similar to the encoding we learned.) By definition, a
program P spreads a virus on input x if
running P with input x causes the operating system to be altered.
It is safe on input x if this doesn’t
happen, and it is safe if it is safe on every input string.
A virus tester is a program IsSafe that when given the input P x,
where P is a program and x is a string,
produces the output “YES” if P is safe on input x and “NO”
otherwise. (We make the assumption that in a string of the form P
x, there is no ambiguity as to where the program P stops.) Prove
that if there
is the actual possibility of a virus, i.e., there is a program and
an input that would cause the operating
system to be altered then there can be no virus tester that is both
safe and correct.
Hint: Suppose there is such a virus tester IsSafe. Then it is
possible to write a program D (for “diago-
nal”) that operates as follows when given a program P as input. It
evaluates IsSafe(P P ); if the result
is “NO”, it prints “XXX”, and otherwise it alters the operating
system. Now consider what D does on
input D.