Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

Question

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.)

Thanks,

Philip

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:

liar's

Russell's/barber

Berry

Quine

Curry's

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.

Answer 1

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).

Answer 2

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.

Answer 3

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.