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.