Computability, noncomputability and undecidability of maximal intervals of IVPs

Graça, Daniel; Zhong, Ning; Buescu, Jorge

http://hdl.handle.net/10400.1/1018

Utilize este identificador para referenciar este registo.

Nome:	Descrição:	Tamanho:	Formato:
06-GZB-noncompode.pdf		213.5 KB	Adobe PDF	Ver/Abrir

Contacte-nos

Autores

Graça, Daniel

Zhong, Ning

Buescu, Jorge

Resumo(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.