3
$\begingroup$

In order to formally ask if a problem is decidable, one first needs to show how to encode each instance of said problem as a finite string of bits (or symbols over some other finite alphabet). For instance, Hilbert's 10th Problem asks us to determine, for a given polynomial $P(x_1,\dots,x_n)$ with integer coefficients, there exists a integer solution to $P(x_1,\dots,x_n) = 0$. One can legitimately ask if this problem is decidable because it is a routine exercise to encode a polynomial with integer coefficients in a form that can be taken as input by a Turing machine, computer program, or any other model of computation.

On the other hand, I have a strong intuition that some problems involving real parameters are "decidable". In fact, already at a fairly early stage, students are tought methods for determining if a quadratic function has two real roots, if $2 \times 2$ matrix is invertible, and so on. This makes me, informally, think that the problem of determining invertibility of $2 \times 2$ real-valued matrices should be considered "decidable".

Is there a general notion of decidibility that would allow one to formalise this intuition?

$\endgroup$
7
  • 4
    $\begingroup$ See "type-2 computability" and "computable analysis" - e.g. here. $\endgroup$ Sep 9, 2021 at 16:56
  • 3
    $\begingroup$ The obvious formalization is “decidability when all the reals are algebraic”, in which case Tarski’s quantifier elimination will show that your examples and indeed all first-order sentences are decidable. Meanwhile many other statements will not be shown decidable in that way, since they are not first-order. E.g.: The Jacobian conjecture over the algebraic numbers is not obviously first-order, since it involves polynomials of arbitrary degree, but in any particular degree Tarski’s algorithm can solve it. $\endgroup$
    – user44143
    Sep 9, 2021 at 17:09
  • 3
    $\begingroup$ Maybe en.wikipedia.org/wiki/Complexity_and_Real_Computation is helpful $\endgroup$ Sep 9, 2021 at 17:27
  • 2
    $\begingroup$ @MattF.: But not all reals are algebraic. $\endgroup$ Sep 9, 2021 at 18:16
  • $\begingroup$ @NoahSchweber Thank you so much for the link! I went through some of the initial sections. They look very promising, although I'm slightly worried by the fact that apparently multiplication by $3$ is not computable. $\endgroup$ Sep 9, 2021 at 21:58

1 Answer 1

6
$\begingroup$

Your intuition betrays you.

Under any reasonable computational model of real numbers, the following are undecidable:

  • Is a real number equal to zero?
  • Is a real number positive?
  • Is a $2 \times 2$ matrix invertible?
  • Does a quadratic equation with real coefficients have two distinct roots?

All of the above have the computational strength of a Halting oracle. For example, here is how one can reduce the Halting problem to zero-testing. Given a Turing machine $T$, define the following sequence of rationals: $$ q_n = \begin{cases} 2^{-n} & \text{if $T$ has not halted by step $n$,} \\ 2^{-k} & \text{if $T$ halts in step $k \leq n$.} \end{cases} $$ In words, $q_0, q_1, q_2, \ldots$ falls off to $0$ for as long as $T$ is still running, and if and when $T$ halts, the sequence stabilizes at a positive value. Because $q_n$ is a computable Cauchy sequence with a computable modulus of convergence, we can compute its limit $x = \lim_n q_n$. Now we have $$x \neq 0 \iff \text{$T$ halts}.$$

Let us talk about the definition of "reasonable":

  1. The usual structure of the field of reals is computable: arithmetical operations $+$, $\times$, $0$, $1$, $-$, ${}^{-1}$.

  2. The order-theoretic structure is computable: $\min$, $\max$, and the strict $<$ is semi-decidable.

  3. An essential characteristic of the reals is that they are complete. A reasonable model of real-number computation therefore provides such a notion. It can be Dedekind completeness (every double-sided real cut determines a unique real), Cauchy completeness (every Cauchy sequence has a limit), or if one is careful enough even MacNielle completeness (an inhabited bounded set has a supremum). However, such completeness must be realized in a computable way. What precisely that means depends on the computational model.

  4. The computational model must be realistic in the sense that it does not enable computations which are not computable in the sense of Turing.

Note that the above conditions do not imply that every real is representable. There are reasonable models in which only the computable reals are accounted for, but also ones that can represent all reals. In every case, the resulting structure is (computably) a complete ordered Archimedean field.

Here are some unreasonable models:

  • Violating computability of basic arithmetic: the usual decimal expansion (because $+$ is not computable).

  • Violating completeness: real closed field, algebraic numbers, fixed-precision floating points.

  • Violating Turing computability: the so-called real RAM model, also known as Blum-Shub-Smale, because it has builtin decidability of $<$ (and therefore also of $=$ and $\leq$).

$\endgroup$
7
  • $\begingroup$ Thank you so much for your answer! It is clearly true that your conditions 1.-4. imply that deciding if a given real number $x$ is positive cannot be decidable. This definitely challenges my previous intuitions. $\endgroup$ Sep 9, 2021 at 21:51
  • $\begingroup$ I'm a little confused by the fact that you insist that every reasonable computational model of the reals must provide some manifestation of completeness, while at the same time not insisting that < should be decidable. If I understand correctly, the reverse is true in the Blum-Shub-Smale model. I suppose it must be one of those cases where intuitions about relative importance of various properties change as one understands the subject better? $\endgroup$ Sep 9, 2021 at 21:55
  • 1
    $\begingroup$ @JakubKonieczny I think that what you want is something like "computable mod real numbers" - computability where you assume that you can test equality of real numbers and do basic computations with real numbers - so for example you can do things like compute the determinant and test if it vanishes. Basically you would want to assume that you can do all the things with real numbers that computers can do with floating point numbers, and build a theory on top of that. I think there is work on stuff like this, it might be what they call "computability over a structure". $\endgroup$ Sep 11, 2021 at 17:11
  • 1
    $\begingroup$ this Feferman paper math.stanford.edu/~feferman/papers/CompOverReals.pdf surveys some of the notions of "computability over a structure" - some of might line up with what you are looking for. $\endgroup$ Sep 11, 2021 at 17:18
  • 1
    $\begingroup$ @ErikWalsberg: you are describing the Real RAM or the Blum-Shub-Smale model. It should be emphasized that this model is non-comptable, unless it is limited to a subfield of reals, such as the algebraic numbers. It is my understanding that an entire field of computational geometry has been built around it, where people imagine that floating points work precisely and correctly (which they do almost all the time, so we have CAD software which kind of works). $\endgroup$ Sep 11, 2021 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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