I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ...correlates precisely with the set of techniques that can be used to prove that the halting problem is undecidable. (I believe the same holds for Godel's first incompleteness theorem, but that might be off-topic.)

A post on another thread (relating to the halting problem), coupled with my interest in recent days in this notion, led me to post this. I am curious as to whether or not the answer to either of the following two meta-mathematical questions is 'yes':

1) Is there a technique that can be used to prove the halting problem that has nothing to do with any paradox?

2) Is there any paradox that cannot be used to prove the halting problem?

For the record, I recently came up with a (slightly garbled, but probably correct) proof that HP is undecidable based on the Unexpected Hanging paradox. I believe that the answer to both of the above questions is 'no,' but I'm not sure how to establish this.

If anyone can offer a counterexample to my claim (on either question), I'd love to hear it. I realize that I've left the term paradox undefined. Ideally, I'd like to think that a reasonable definition of paradox might be crafted in terms of the halting problem.

(Also, I've always been curious as to whether or not there's a way to express paradoxes mathematically...that's another part of the motivation for asking this. I've always wondered if there is any way to figure out precisely how many "basically distinct" paradoxes there are, and if there's a way to prove how many there are.)



EDIT: I'm trying to clarify, because some posters think that my question is off-topic. What I am referring to is the notion that a paradox, such as the liar's paradox, the Berry paradox, unexpected hanging paradox, etc., could be used intuitively as a guide for proving the Halting problem. As an example, Turing used logic similar to Godel's in proving that the halting problem is undecidable; in that sense, I think one could argue that this halting problem proof is "based on" the liar's paradox. The question, again, is: is there any paradox that cannot be used to prove THP, or any proof that doesn't use a paradox?

If you believe that this is somehow less on-topic to TCS than, say, the Baker-Gill-Solovay result, please let me know why you think so.

EDIT #2: I am now trying to more clearly define what I mean by a "paradox." By a paradox, I mean a natural language situation, idea, or sentence that is intuitively and inherently contradictory. In a Wikipedia article, they refer to this type of paradox as an "antimony."

I'm not referring to paradoxes that do not lead to an inherently absurd seeming result; i.e., I have no interest in the Obama paradox, or even less blatant paradoxes such as the chicken-and-the-egg paradox. I am also not interested in paradoxes that seem philosophical but not logical, e.g., Zeno's paradox.

It's difficult to really nail down what I mean by "paradox," so here's a partial list of paradoxes that are relevant:






Most, but not all of the paradoxes listed in this Wikipedia article under the heading of "Logic" other than vagueness are relevant. Another question I am wondering about is Newcomb's paradox, or the psychic paradox.

Thanks to anyone who has any ideas on this. In particular, one way to answer the question that I would appreciate is: Can you come up with a reasonable way to define/capture the notion of paradox that I'm referring to?

I apologize if this question, as originally asked, was vague or unclear.

  • 1
    $\begingroup$ Russell's paradox, at least, is a paradox in a very well-defined sense: it shows that there is an inconsistency (a way to derive a contradiction) in a particular formal system (Wikipedia calles it "the naive set theory of Richard Dedekind and Frege"). I don't necessarily think this question is on-topic for TCS if you're asking about paradoxes in any sort of vague, natural-language sense. $\endgroup$ – Rob Simmons Nov 9 '10 at 21:55
  • $\begingroup$ I had thought it was on-topic because I was asking about the use of paradoxes, or the "idea behind them," to discuss applications to the proof of the halting problem. I would argue that it's meta-mathematical but on-topic; why does a question regarding paradoxes qualify the subject as off-topic? I'm wondering if it's possible to prove the halting problem without the use of paradoxes, and if there's any paradox that can't be adapted into a proof of the halting problem. $\endgroup$ – Philip White Nov 9 '10 at 21:58
  • $\begingroup$ I think I understand the thought behind your reasoning now, and +1ed Andrej's answer below. I think it's just a bit of a "soft question" (that's fine, there's even a soft-question tag!) because you've clearly left the definition of "paradox" too open-ended to definitively answer your question. Try googling "Obama paradox" or "evaporation paradox," for example. $\endgroup$ – Rob Simmons Nov 10 '10 at 0:19
  • $\begingroup$ Haha, I hadn't been aware of the Obama paradox. I had tried gave a few examples; I'll try to more narrowly define what I mean by paradox in a moment $\endgroup$ – Philip White Nov 10 '10 at 0:21
  • $\begingroup$ You might also want to read the related MO question mathoverflow.net/questions/32824/… $\endgroup$ – András Salamon Nov 10 '10 at 0:35

It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments. Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the main diagonal arguments back in 1969, including Cantor's and Rice's Theorems, the halting problem, and Gödel's first incompleteness theorem.

Yanofsky's 2003 tutorial discussion A Universal Approach to Self-referential Paradoxes, Incompleteness and Fixed Points provides a nice overview of Lawvere's ideas (arXiv:0305282).

More recently, Samson Abramsky and Jonathan Zvesper have been taking this further (arXiv:1006.0992).

  • $\begingroup$ Great, thank you. I'm looking at a couple of these and they seem very relevant. Additionally, I'm interested in the Brandenburger-Keisler paradox, which is referenced in the third link. $\endgroup$ – Philip White Nov 10 '10 at 0:42

It looks like you want a confirmation of your opinion that classical paradoxes have something to do with the Halting Problem. This is the case on some vague level as most well-known paradoxes rely on a form of self-reference, and so do the usual proofs of the Halting Problem. But to be more precise, we would have to understand what it means "to use a paradox in solution of the Halting Problem".

Have you looked at the article on Self-reference at the Stanford Encyclopedia of Phylosophy? In particular, section 2.4 seems to address your question quite well. The article also describes the mathematical ideas that can be used to treat the paradoxes. I recommend it.

  • $\begingroup$ In fairness, you're more or less correct...I was hoping someone could either verify or refute my claim. I'll take a look at the source you mentioned, thank you. $\endgroup$ – Philip White Nov 9 '10 at 23:20

I agree that you are not exactly on topic, given the extreme vagueness of your question. I believe what you might be thinking about when you talk about paradoxes is called a diagonalization argument. The question "can the halting problem be proved undecidable without a diagonalization argument" is better defined. I do not think there is any such proof.

  • 2
    $\begingroup$ I had heard that Godel's incompleteness theorem is provable using the Berry paradox in a fashion that does not use diagonalization. I would imagine that a similar technique could be used to prove the halting problem undecidable. So, I don't think diagonalization and paradoxes are the same thing. $\endgroup$ – Philip White Nov 9 '10 at 22:36

Your Answer

