Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". I regard the following as the standard definition:

Let $P(n)$ be a statement like "$n$ has at least three prime factors" or "the $n$th Turing machine halts" (we can also forget the statement and consider just its "truth value" function $P:\mathbb N\to\{0,1\}$). We say that the problem $P(n)$ is undecidable iff there is no Turing machine which answers "Is $P(n)$ true" correctly for all $n$ (equivalently, iff the function $P:\mathbb N\to\{0,1\}$ is non-recursive).

On the other hand, there is also the following alternative notion:

Let $P$ be a statement like "$\forall x,y,z,n\in\mathbb Z,x^n+y^n+z^n=0\;\&\;n\geq 3\implies xyz=0$". We say that the problem $P$ is undecidable iff it is independent of some particular chosen set of axioms (like PA or ZFC).

I would prefer to call this notion "independent of PA" or "independent of ZFC", since it makes explicit reference to a particular choice of axiomatic system.

Is there a good reason to use "undecidable" for both of these notions? Has this collision of terminology bothered anyone else? Is there a deeper connection between these notions which justifies using the same word for both?

share|improve this question
1  
If your theory $T$ is computably axiomitizable (as is PA and ZFC and everything nice) then there is a decision procedure to determine $T \vdash \varphi$, namely search for a proof of $T \vdash \varphi$ and $T \vdash \neg \varphi$. This will halt iff $\varphi$ is not independent of $T$. With Gödel's and Tarski's theorems, the theory of the natural numbers (all statements true of the natural numbers) is not a decidable set of sentences. However, some theories like the theory of real closed fields (all true first order sentences of the real numbers) is decidable. –  Jason Rute May 16 '13 at 5:52
1  
Your sentence is missing a quantifier over $n$. Is the idea to determine for which $n$ this sentence is true (or provable over say PA)? Then it is a decision problem in the first sense. –  Jason Rute May 16 '13 at 6:00
    
Do you have a specific reference in mind? –  Jason Rute May 16 '13 at 6:12
    
@Jason Rute: Thanks, I do mean quantified over all $x,y,z,n$ in the second example. –  John Pardon May 16 '13 at 16:20
add comment

5 Answers

I agree that the collision of terminology can be confusing; I was confused by it myself when learning the subject, and I frequently find myself having to straighten out others who are confused by it. However, there certainly are close connections between the two notions, so it is not just an unfortunate accident.

(As a preliminary remark, let us note that there is theoretically no collision of terminology because undecidability in the algorithmic sense applies to a family of strings (in particular, the computational problem of determining whether a given string lies in the family) whereas undecidability in the logical sense applies to a single string (in particular, whether the string is a theorem of some fixed axiomatic system). So for example if you ask, "Is the continuum hypothesis undecidable in ZFC?" there can be no ambiguity about which sense of the word is intended since there is only one string in sight.)

There is a historical reason why the two senses of "undecidable" are closely related. In some sense the "ultimate" decision problem is the problem of determining whether a given mathematical statement is true or not. In the old days one could dream of an algorithmic solution to this problem. The shattering of this dream may therefore reasonably be dubbed the "undecidability phenomenon." But there are different ways of explaining why the dream failed, so we get slightly different senses of the word "undecidable" falling out.

More specifically, if you mentally transport yourself back to pre-Goedelian days and conflate truth with provability, then you can phrase what I called the "ultimate" decision problem as the problem of determining whether a given statement $Q$ is a theorem of a given axiomatic system. This is what Hilbert called the Entscheidungsproblem ("decision problem" in German). Note that there is an obvious candidate algorithm for solving this problem: Just enumerate all proofs from the axioms in a systematic manner until either $Q$ or $\neg Q$ shows up as a theorem. Why doesn't this work? Well, one answer is that Goedel showed that there exist statements for which this process will never terminate. So you could make the case that the "undecidability phenomenon" is traceable to the existence of "logically" undecidable statements. On the other hand, as Church and Turing independently showed, even if you allow arbitrary algorithms (not just the obvious candidate), there is still no algorithmic solution to the Entscheidungsproblem. Turing showed this by reducing the halting problem to it. Though Turing did not use the word "undecidable" in his paper, you can see why people came to use the word "undecidable" for algorithmic unsolvability.

We can say more; the connection between the two notions of undecidable is not "merely" their common historical roots in the Entscheidungsproblem. For example, one way of proving Goedel's incompleteness theorem is by way of computability theory. As Martin Davis succinctly sketched it, you can argue that the set of arithmetic theorems of any formal system is recursively enumerable, while the set of arithmetic truths is not, so any sound formal system must fail to prove some arithmetic truth. Less precisely but more suggestively, in some sense the "reason" there are logically undecidable statements is that there is no decision procedure for truth. So even though the two notions of undecidability are distinct, I think that it's reasonable to keep using the same term for both, to remind us of these close connections.

share|improve this answer
add comment

To my way of thinking, the two notions of undecidability are closely related, and the associated undecidability phenomenon and independence phenomenon, which are both pervasive in mathematics, are deeply inter-twined.

The reason is that every Turing undecidable set is saturated with logical undecidability. If we describe a certain undecidable property of finite graphs, say, then there will be infinitely many specific finite graphs for which it will be logically undecidable, even with respect to very strong theories such as ZFC+large cardinals, whether that finite graph has the property or not. And similarly with any undecidable set $A$ and consistent c.e. theory $T$. This is because if almost all instances of "$n\in A$?'' were settled by $T$, then we would have a decision procedure for $A$, namely, on input $n$, search for a proof from $T$ whether $n\in A$ or not (and hard-code the finitely many exceptions).

So every Turing undecidable property is accompanied by a huge assortment of logically undecidable statements, assertions about whether particular objects have the property or not, which are independent of whichever fixed consistent background theory you care to adopt.

So although the two undecidability phenomenon are distinct, I find them to be deeply connected.

share|improve this answer
    
Is this still true for consistent but untrustworthy theories that prove false results? –  Will Sawin May 19 '13 at 4:43
    
No, the argument relies on you regarding the background theory $T$ as true, since you want to be able to know that when $T$ proves that $n\in A$, that $n$ really is in $A$ as you had meant it. The point is that if $T$ is what you believe is true (and it is consistent and c.e.), then any computably undecidable set $A$ will have many instances of logical undecidability. –  Joel David Hamkins May 19 '13 at 10:04
add comment

My opinion is that the answer to your question is "no;" these are fundamentally different concepts, and should be called by different names.

The first kind of undecidability you mention is absolute: it doesn't depend on an ambient theory. Of course, the second kind of undecidability is relative to a specific theory, and given any proposition $p$ there is some true axiomatizable theory $T$ which decides it (e.g., either $PA\cup\lbrace p\rbrace$ or $PA\cup\lbrace\neg p\rbrace$). The absolute version is much stronger, in the following sense: if $P(x)$ is a formula which is undecidable in the first sense, then for any axiomatizable true theory $T$, there must be some $m$ such that $P(m)$ is undecidable (in the second sense) in $T$.

I think the only sense in which these two notions are closely related is that historically they come out of the same machinery: Goedel's 1931 paper for the second sense of undecidability and Turing's 1936 paper for the first sense both use the same idea of representing computational systems inside the language of arithmetic. Besides this, though, the substance of the two notions is completely different (at least, that's my perspective; I'd be interested if anyone disagrees).

(One last thought: really, the first sense of undecidability is a special case of the more broad notion of "non-computable function." Proving the existence of a non-computable function just takes a counting argument; getting a definable non-computable function, which is what your first notion of undecidability is essentially talking about, takes more work.)

share|improve this answer
    
Noah, one comment. Gödel's theorem says that provability (in PA, ZFC) is undecidable. Tarski's theorem says that truth is undecidable. I think both senses of undecidable, while technically different, are closely connected and really two sides of the same coin. (Although I wouldn't say that a single sentence is "undecidable". I can't tell if that is what the OP is doing in the second example.) –  Jason Rute May 16 '13 at 6:22
    
So I interpreted "provability" as an instance of the OP's first sense of undecidable, and the second instance being about an individual sentence (and "truth" as neither since Tarski shows that truth is undefinable - I don't think Tarski actually showed that truth was undecidable per se, that requires the coding of computable functions into arithmetic). Maybe I was wrong? –  Noah S May 16 '13 at 6:31
    
Silly me, I was mixing up "definability" and "decidability". (I agree the answer depends on how to interpret what the OP means in the second case.) –  Jason Rute May 16 '13 at 7:04
2  
Noah, why do you find computable undecidability to be absolute? Surely the question of whether a given set is undecidable or not can itself be independent of PA or whatever background theory. Consider the property "$p$ halts before the length of the shortest proof of a contradiction in ZFC". If Con(ZFC) holds, then this is the halting problem and hence undecidable. But otherwise, it is decidable. The the Turing decidability of that set is independent of ZFC. –  Joel David Hamkins May 16 '13 at 10:48
1  
@Joel: I didn't mean "absolute" in the formal sense. My point was just that saying that a proposition is independent of a formal system is clearly relative to that formal system. If we're platonists for a second (which, granted, I tend not to be), then by contrast every set of natural numbers is either computable or incomputable. The only role a theory plays here is telling us which case it is. Two people with different formal systems might disagree on whether a set of natural numbers is computable or not, but they'd still have in mind the same definition of "computable." –  Noah S May 16 '13 at 15:22
show 7 more comments

I am going to skip the number theory and concentrate on computability, in particular

"the $n$th Turing machine halts" (we can also forget the statement and consider just its "truth value" function $P:N\to\{0,1\}$.

It is completely inappropriate to use a discrete two-element set for the "truth values" of such a proposition.

We can swap $0$ and $1$.

We cannot swap the statements "the $n$th Turing machine halts" and "the $n$th Turing machine runs forever". They are fundamentally different: we can just wait for the first to happen and then if it does we know that it is true. We can never know that the second is true.

Granted, you can add an oracle to your Turing machine that can say whether the $n$th ordinary Turing machine halts, but it does not answer the question for the enhanced machine. A similar argument applies to "Turing machines" for (finding proofs in) stronger logical theories, which I guess is what the second question and Noah's answer are about.

However, the point that I want to make here is that a gratuitous confusion is introduced in the meanings of words like decidable and recursive by imposing two-valued logic on them. At least say semidecidable and semirecursive (or, better, semicomputable).

In the case of computable functions, the Kleene normal form theorem says that any semicomputable predicate $\phi(n)$ is of the form $$ \phi(n) \iff \exists h.T(p,n,h) $$ for some code $p$, where $T$ is a (standard) decidable ternary predicate.

This means that, in the appropriate truth-value object for such predicates, which I call $\Sigma$, any truth value is a computable disjunction of decidable ones ($\bot$ and $\top$).

Reconsidering the second question, trying to prove that a statement follows from a given theory is like running a Turing machine to search all possible proofs.

(This is a pretty daft way of doing mathematics, but then computability theory was traditionally written in a similarly infeasible manner. With small modifications it can be made to look much more like modern practical computation. Using binary trees instead of integers makes a huge difference.)

If we are going to discuss which symbols to use for true and false then I suggest the following. In the second question there is an object language (statements that might be deduced from theories) and a metalanguage (searching for proofs). We might think of the object language as a kind of algebra, so it makes sense to write $0$ and $1$ for its truth values, especially if the theory under discussion is a classical one.

In the metalanguage success and failure are not interchangeable ideas, so my $\bot$ and $\top$ are preferable and they certainly belong to the space $\Sigma$ and not a two-element discrete set.

In other words, the confusion to which the original question referred is slightly sloppy language based on fundamentally the same idea. Imposing two-valued logic on termination of computations is also a misuse of language, but in my opinion one that seriously obstructs understanding.

share|improve this answer
6  
Why is it completely inappropriate to use true (1) and false (0)? Is this for a philosophical reason? I think what the OP means is we care about computing the predicate P(n) which is an equivalent problem if the 0s and 1s were swapped. In other words if we can compute P(n), we can compute 1 - P(n). (Semicomputability is different, but that wasn't the OP's question.) –  Jason Rute May 16 '13 at 6:39
    
You can write 1 and 0 for true and false if you wish, but the space of all truth values is not $\\{0,1\\}$, it is something a little bigger and asymmetric. –  Paul Taylor May 16 '13 at 7:02
    
I have tried twice to write braces around $(0,1)$ in that. –  Paul Taylor May 16 '13 at 7:03
    
You need to put backticks around the LaTeX for brackets to work. (See the note on the right sidebar.) –  Jason Rute May 16 '13 at 7:43
    
You cannot solve the Halting Problem by writing $1-P(n)$. Termination and non-termination of programs (or of searches for proofs) are fundamentally different things. I seem to be being down-voted for the heresy of denying Excluded Middle in the situation where it most blatantly conflicts with common sense. –  Paul Taylor May 18 '13 at 14:34
add comment

Yes, the undecidability and independence phenomena are closely interrelated, and though both Professors Hamkins and Chow gave good answers to 'unknown's' question, they only hinted at exactly how they are related. I will attempt to show how they are related.

As my answer I will give an example found in Hartley Rogers, Jr.'s text THEORY OF RECURSIVE FUNCTIONS AND EFFECTIVE COMPUTABILITY (found in section 7.8 of his book), that of Elementary Arithmetic. The well-formed formulas of Elementary Arithmetic are those which can be built up from +, X, =, the constants 0,1,2,3,..., variable symbols for nonnegative integers, quantifiers over nonnegative integers, and the sentential connectives 'NOT', &, 'OR', -->,<-->: subject to the requirement that every variable in a well-formed formula be acted upon by some quantifier. Rogers then claims that "it is possible to define the set of 'true' well-formed formulas [wffs--my comment] of elementary arithmetic in a way that is straightforward and entirely in accord with our intuition." He then goes on to distinguish between true wffs and false wffs of elementary arithmetic and from there goes to prove the following two statements

  1. The true wffs of elementary arithmetic form a productive set (a non-r.e. set).
  2. The false wffs of elementary arithmetic from a productive set.

In a footnote on pg. 97, Rogers shows how Peano Arithmetic is defined in the language of elementary arithmetic (this is important because now one can distinguish between sentences in elementary arithmetic that are provable in PA and those that are not). He then goes to show that by making the "special assumption" that "no false wffs of elementary arithmetic are provable" (i.e. that PA is consistent) one can prove these two statements:

1'. The unprovable wffs form a productive set. 2'. The provable wffs form a creative (and therefore not recursive) set [a creative set is a set that is recursively enumerable (r.e.) whose complement is productive]

It should be noted that since elementary arithmetic allows quantification over the nonnegative integers only (the constants 0,1,2,3,....), the language of elementary arithmetic is a first-order language and any formal theory therein defined is a first-order theory.

Since elementary arithmetic is a first-order language (and PA is a first-order theory), one can apply the Godel Completeness Theorem (in its several forms) to derive how to use models to show (for example) sentences unprovable in PA are independent of PA.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.