As part of an exercise I've been given the assignment to find the complement of the following statement:
L = {P⊆{0,1}*: P is a legal encoding of a C program, and P terminates on all but a finite set of inputs}
The way I approached the question is as follows,
X = P is a legal encoding of a C program
Y = P terminates on all but a finite set of inputs
Thus the statement I have to find the complement for is X AND Y which means
NOT(X AND Y) = NOT(X) OR NOT(Y)
now this is the part where I'm hitting a wall,
NOT(X) = P is not a legal encoding of a C program
NOT(Y) = ???
I honestly am not sure as to how to negate that statement, I've been thinking about several statements as follow:
1. there exists a non finite set of inputs which P does not terminate on
2. there exists a finite set of inputs which P does terminate on
3. 1 OR 2 (logical OR)
4. something else?
Will appreciate any assistance or suggestion!
Let $I_P$ be the set of inputs for $P$. I can rephrase $Y$ as: There exists a finite set $N\subset I_P$ such that $P$ does not terminate on $N$, and such that $P$ terminates on $T=I_P-N$ (the set difference, the set of inputs not in $N$).
The negation $\text{NOT}(Y)$ of this statement is: There does not exist a finite set ... and so on as above, but if there does not exist such a finite set, then the set of inputs for which $P$ does not terminate, must be infinite.
So $\text{NOT}(Y)$ ends up as: There exists an infinite set $N\subset I_P$ such that $P$ does not terminate on $N$, and such that $P$ terminates on $T=I_P-N$ (the set difference, the set of inputs not in $N$).
Or in short (and informally): $P$ doesn't terminate for an infinite number of inputs.