6
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Some Observations on Infinitary Complexity

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Continuing the study of complexity theory of Koepke's Ordinal Turing Machines (OTMs) that was started by Rin, L\"owe and the author, we prove the following results: (1) An analogue of Ladner's theorem for OTMs holds: That is, there are languages \(\mathcal{L}\) which are NP\(^{\infty}\), but neither P\(^{\infty}\) nor NP\(^{\infty}\)-complete. This answers an open question of \cite{CLR}. (2) The speedup theorem for Turing machines, which allows us to bring down the computation time and space usage of a Turing machine program down by an aribtrary positive factor under relatively mild side conditions by expanding the working alphabet does not hold for OTMs. (3) We show that, for \(\alpha<\beta\) such that \(\alpha\) is the halting time of some OTM-program, there are decision problems that are OTM-decidable in time bounded by \(|w|^{\beta}\cdot\gamma\) for some \(\gamma\in\text{On}\), but not in time bounded by \(|w|^{\alpha}\cdot\gamma\) for any \(\gamma\in\text{On}\).

          Related collections

          Most cited references 6

          • Record: found
          • Abstract: found
          • Article: not found

          Infinite time Turing machines

          We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every set. for example, is decidable by such machines, and the semi-decidable sets form a portion of the sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
            Bookmark
            • Record: found
            • Abstract: not found
            • Book Chapter: not found

            An Enhanced Theory of Infinite Time Register Machines

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              Infinite Time Register Machines

               Peter Koepke (2006)
                Bookmark

                Author and article information

                Journal
                30 January 2018
                Article
                1801.10027

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                math.LO

                Comments

                Comment on this article