Flaw in self-referential proof that all languages are undecidable

499 Views Asked by At

I am looking for a flaw in the following incorrect proof, which attempts to prove that all languages are undecidable:

Proof: Suppose for contradiction that there is a decidable language $L$. Then there is some decider $D$ for the language $L$ which we may represent by a function written in code called doesAccept(). We may construct the following self-referential program whose code is as follows:

string i = mySource();
string in = getInput();
if (doesAccept(i,in)){
reject();
} else{
accept();
}
}

Whether or not our program accepts some input string $w$, we reach a contradiction. For instance if our program accepts $w$, then doesAccept(i,in) returns true, our program rejects $w$ and we reach a contradiction. Likewise, if our program does not accept $w$, then our program accepts, which again is a contradiction. Then our assuption must be wrong and no languages are decidable.

Here are my thoughts as to the flaw:

The proposed proof assumes that there is some decidable language $L$ but not necessarily one which accepts a string containing the program i.e., $\langle i,in \rangle$. Am I on the right track?

1

There are 1 best solutions below

0
On BEST ANSWER

As pointed out in the comments: the language your program accepts does not need to be the one of the decider D. Rather you seem to accept the complement. There is nothing wrong with that. Starting from a decidable language you show that you can construct a program that accepts its complement. This is in accordance with the fact that the decidable languages are closed under complement.

So the flaw is where you say "our program rejects w and we reach a contradiction" - the fact that D and your program produce distinct results is not in contradiction to any of your assumptions.

Also spaceisdarkgreen's comments are important. A decider for a given language does not need to take any program's code as input. It has the code for one given language. This also indicates that you have not completely understood some concepts here.