Are the two meanings of "undecidable" related?

Question

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?

Answer 1

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.

Update. Let me clarify exactly how much we need to trust the theory for this argument to work.

Theorem. If $A$ is any computably enumerable computably undecidable set and $T$ is any consistent theory extending PA, then there are numerous instances of $n\notin A$ such that $T$ does not prove this. Consequently, if $T$ is $\Sigma_1$-sound, then these membership statements are independent of $T$.

Proof. Notice first that if $n\in A$, then PA and hence also $T$ will prove this. Therefore by consistency, $T$ is reliable in any proof of $n\notin A$. Consider the algorithm that on input $n$ undertakes the following: during the day, it enumerates $A$ and searches for whether $n$ appears; at night, it searches for a proof in $T$ that $n\notin A$. If all instances of nonmembership were provable, this would be a computable decision procedure for $A$, contrary to assumption. So there must be many nonmembers of $A$ such that this fact is not provable in $T$. If also $T$ is $\Sigma_1$-sound, then it follows that the statement $n\in A$ is independent of $T$. $\Box$

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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