Verifying time complexity of Turing machines

DOI10.1016/J.TCS.2015.07.028MaRDI QIDQ496007zbMATH OpenOpenAlexFDO

Authors David Gajser

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3648

zbMATH Keywords

Turing machineregular expressionrunning timecrossing sequencedecidable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: We show that, for all reasonable functions $T(n)=o(nlogn)$, we can algorithmically verify whether a given one-tape Turing machine runs in time at most $T(n)$. This is a tight bound on the order of growth for the function $T$ because we prove that, for $T(n)geq(n+1)$ and $T(n)=Omega(nlogn)$, there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most $T(n)$. We give results also for the case of multi-tape Turing machines. We show that we can verify whether a given multi-tape Turing machine runs in time at most $T(n)$ iff $T(n_0)<(n_0+1)$ for some $n_{0}inmathbbN$. We prove a very general undecidability result stating that, for any class of functions $mathcalF$ that contains arbitrary large constants, we cannot verify whether a given Turing machine runs in time $T(n)$ for some $TinmathcalF$. In particular, we cannot verify whether a Turing machine runs in constant, polynomial or exponential time.

Recommendations

• Verifying whether one-tape Turing machines run in linear time
• scientific article; zbMATH DE number 17549
• SOFSEM 2004: Theory and Practice of Computer Science
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• scientific article; zbMATH DE number 3319549 (Why is no real title available?)
• Arithmetical hierarchy and complexity of computation
• Computational Complexity
• Computational Complexity of One-Tape Turing Machine Computations
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• One-tape, off-line Turing machine computations
• Theory of one-tape linear-time Turing machines

Cited in

(3)

• Weight-reducing Turing machines
• Running Time Complexity of Printing an Acyclic Automaton
• Verifying whether one-tape Turing machines run in linear time

This page was built for publication: Verifying time complexity of Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496007)