Publication
Computability, noncomputability and undecidability of maximal intervals of IVPs
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 213.5 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Let (α, β) ⊆ R denote the maximal interval of existence of solution for
the initial-value problem
dx
dt = f(t, x)
x(t0) = x0,
where E is an open subset of Rm+1, f is continuous in E and (t0, x0) ∈
E. We show that, under the natural definition of computability from
the point of view of applications, there exist initial-value problems with
computable f and (t0, x0) whose maximal interval of existence (α, β) is
noncomputable. The fact that f may be taken to be analytic shows that
this is not a lack of regularity phenomenon. Moreover, we get upper
bounds for the “degree of noncomputability” by showing that (α, β) is
r.e. (recursively enumerable) open under very mild hypotheses. We also
show that the problem of determining whether the maximal interval is
bounded or unbounded is in general undecidable.