Decidability theory involving real parameters 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?
 A: 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":

*

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


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


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


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