Skip to Main content Skip to Navigation

# Achilles and the tortoise climbing up the hyper-arithmetical hiearchy

1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we characterize the computational power of dynamical systems with piecewise constant derivatives (PCD) considered as computational machines working on a continuous real space with a continuous real time: we prove that piecewise constant derivative systems recognize precisely the languages of the ${\omega ^{k}} ^{th}$ (respectively: ${\omega ^{k}+1} ^{th}$) level of the hyper-arithmetical hierarchy in dimension $d=2k+3$ (respectively: $d=2k+4$), $k \ge 0$. Hence we prove that the reachability problem for PCD systems of dimension $d=2k+3$ (resp. $d=2k+4$), $k \ge 1$, is hyper-arithmetical and is $\Sigma_{\omega ^{k}}$-complete (resp. $\Sigma_{\omega ^{k}+1}$-complete).
Mots-clés :
Document type :
Journal articles
Domain :
Complete list of metadata

https://hal.inria.fr/inria-00100818
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:51:33 PM
Last modification on : Friday, February 26, 2021 - 3:28:05 PM

### Identifiers

• HAL Id : inria-00100818, version 1

### Citation

Olivier Bournez. Achilles and the tortoise climbing up the hyper-arithmetical hiearchy. Theoretical Computer Science, Elsevier, 1999, 210 (1), pp.21-71. ⟨inria-00100818⟩

Record views
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8681727647781372, "perplexity": 8082.820637310112}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-21/segments/1620243991488.53/warc/CC-MAIN-20210515223209-20210516013209-00485.warc.gz"}