Verifying time complexity of Turing machines

DOI10.1016/J.TCS.2015.07.028zbMATH Open1329.68111arXiv1307.3648OpenAlexW850465257MaRDI QIDQ496007FDOQ496007

David Gajser

Publication date: 16 September 2015

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

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.

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

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

zbMATH Keywords

Turing machineregular expressionrunning timecrossing sequencedecidable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Computational Complexity
• Title not available (Why is that?)
• Arithmetical hierarchy and complexity of computation
• Theory of one-tape linear-time Turing machines
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity of One-Tape Turing Machine Computations
• Title not available (Why is that?)
• One-tape, off-line Turing machine computations

Cited In (3)

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

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)