Goedel's Incompleteness Theorem says that no system of axioms is complete. There are always propositions that can be formed within the system, which cannot be proved true or false. If the system of axioms is expanded in order to determine the truth value of the proposition, the new axioms introduce the ability to form new propositions whose truth cannot be known. This has deep implications in many fields of knowledge.

The proof of this theorem is beautifully simple:
1. Suppose there is a universal truth machine that can truthfully answer every question. Call it the UTM.
2. You tell the UTM: "G is this proposition, which the UTM will never say is true."
3. You then ask the UTM: "Is G true or false?"
4. The UTM cannot say that G is true. If the UTM answers that G is true, then G must be false. But if G is false, the UTM would have been wrong since it said G was true. Thus, the UTM can never say G is true.
5. Now you now know that G is true - precisely because the UTM will never say it's true.

NOTE: The UTM will never say the G is false either. This is not essential to the proof but interesting nonetheless. If the UTM says G is false, then the UTM never says it's true, which makes G true (and the UTM wrong).

This proves that a UTM cannot exist, because there is always at least one proposition it cannot answer. And that is sufficient to proving Godel's incompleteness theorem.

Actually, Goedel's theorem goes further than this. Not only was there a meaningful statement the UTM could not know, but that statement was indeed true, and we could know it even though the UTM could not.

But, being the skeptic that I am, I suspect the proposition G is somehow invalid - perhaps because it refers to itself. But Godel proved that G is a valid proposition. He did this by formulating a polynomial that has a solution if and only if G is true. This shows that G is not some kind of nonsense, but despite being self referential, it is a valid mathematical proposition. And, it is a proposition whose truth we know, even if the UTM cannot.

I do not understand how Godel formed this polynomial, but apparently he did and it survives the scrutiny of mathematicians to this day.

Now what does this have to do Searle's Chinese Room?

The program in the Chinese room is finite. This program is not complete or universal, nor does it claim to answer every question truthfully. However, the program itself, like any program, is a system of axioms. Thus Godel's theorem tells us there are statements that it cannot answer. Of course, it can still reply to questions it doesn't understand, for example by generating a random response. But there must be statements that trigger this.

We can assume the tester can identify a random response. Perhaps not always, since a random response could accidentally be meaningful or even correct. But that has low probability. It is more likely that the tester will identify a random response.

Godel's theorem tells us that there must exist some question the tester can ask, which will trigger a response from the Chinese Room that is not meaningful (at best random). The goal of the tester is to find this question, ask it, and analyze the answer to determine which room has the computer and which has the Chinese speaking person.

So I believe Godel's theorem tells us the Chinese Room is solvable. The question remains how to solve it. What question (or series of questions) can be asked?