4

My textbook on mathematical logic states: "every decidable set is enumerable", and that it is decidable if and only if it is enumerable and its complement is also enumerable.

Decidable is defined roughly as:

$W$ (subset of $A$) is decidable if there is a procedure that for every element in $A$ determines if it is in $W$ or not.

The proof for this is very simple, but it seems to use the assumption that its superset $A$ is countable.

So here's my question: If $A$ is not countable, then is it possible for a subset $W$ of $A$ to be decidable, even though the complement of $W$ is not enumerable?

I would say yes, with the following proof: take the set of real numbers within the interval $[1,2]$, excluding $2$. This set is decidable: a number $1.xxx$ where $xxx$ are arbitrary amount of arbitrary digits is in the interval. Any other number is not in the interval. Yet we cannot enumerate it or its complement, since the reals are uncountable.

Correct?

Luca Bressan
  • 6,845
user56834
  • 12,925

1 Answers1

4

One one hand, that theorem in your book is referring only to sets of natural numbers, which is the context of introductory computability theory. Computability is not concerned with arbitrary sets, but only ones whose elements can be passed in to a Turing machine. The basic case, which is what intro books focus on, is when we are looking at computability of sets of naturals. So you can't read "set" in that result to refer to arbitrary sets; that isn't the intention.

The example of real numbers does not hold up. As an example, the interval $[0,2)$ was claimed to be decidable. Imagine that you see larger and larger initial segments of a single number: $1.9$, $1.99$, $1.9999$, etc. You have to eventually say if this number is in $[1,2)$. Of course, this is impossible for an algorithm: the number might be equal to $2$, or it might end up less than $2$, and there is no way to tell which of these happens in a finite amount of time. We can show, actually, that the only decidable sets of real numbers are the entire real line and the empty set.

However, if we move to a different space, then the answer will be "yes". Work with the space of all infinite sequences of $0$s and $1$s. Let $S$ be the set of sequences whose first element is a $0$. This is a decidable set, because the algorithm just needs to look at the first element to decide if an infinite sequence is in the set. The complement is the set of all infinite binary sequences which start with $1$. That is an uncountable set, so it can't be enumerated in the sense you have in mind. Neither can the set of all sequences that start with $0$, so the decidable set itself is not enumerable in the sense you have in mind.

There is a deeper issue, though. When we look at subsets of the natural numbers, the following are equivalent properties of a set $S$:

  • The set $S$ is enumerable
  • The set $S$ is the range of a total computable function
  • The set $S$ is the domain of a total computable function

When we start looking at computability on other, uncountable sets, we often use the third bullet as the definition of "enumerable", rather than the second. With that change of definition, it becomes true again that every decidable set is enumerable.

Carl Mummert
  • 81,604
  • How can you look at the first element of a sequence $s$ if $s$ is not a computable function from $\mathbb{N}$ to ${0, 1}$? Indeed, such an $s$ exists because there are uncountably many sequences starting with $0$, but only countably many of them are computable. – Luca Bressan Sep 14 '16 at 11:34
  • In the standard model of Turing computability, the digits of the sequence are written on an "oracle" tape before the Turing machine is started. In this way we can talk about passing arbitrary infinite binary sequences as inputs. The input itself need not be computable. – Carl Mummert Sep 14 '16 at 17:38
  • I see. But then, I don't understand why the only decidable subsets of $\mathbb{R}$ are $\varnothing$ and $\mathbb{R}$ itself. We could represent any real number $x$ as an infinite sequence made of three parts: sign, integer part of $\lvert x \rvert$, fractional part of $\lvert x \rvert$. Then I'd say that $(-\infty, 0)$, ${ 0 }$ and $(0, \infty)$ are decidable: the machine just needs to look at the string encoding the sign (which is either $-$, $0$ or $+$), the length of which is bounded by a constant. What am I missing? – Luca Bressan Sep 14 '16 at 18:31
  • Because every computable function from the real line is continuous, any computable function from the reals to ${0,1}$ is constant. The issue in your post is that there is no way to tell whether the fractional part is zero. However the standard way to represent a real is as a quickly converging Cauchy sequence of rationals. – Carl Mummert Sep 14 '16 at 20:06