Verifying Time Complexity of Turing Machines

Abstract

This paper presents a summary of the doctoral dissertation of the author, which analyzes in detail the following problem. For a function T that maps non-negative integers to non-negative reals, how hard is it to verify whether a given Turing machine runs in time at most T(n)? Is it even possible?

References

D. Gajser. Verifying Time Complexity of Turing Machines. FMF UL, 2015. Thesis also available on ECCC.

D. Gajser. Verifying time complexity of Turing machines. Theor. Comput. Sci., 600: 86 - 97, 2015.

D. Gajser. Verifying whether one-tape Turing machines run in linear time. ECCC, TR15-036, 2015.

G. Pighizzini. Nondeterministic one-tape off-line Turing machines and their time complexity. J. Autom. Lang. Comb., 14(1): 107 - 124, 2009.

Authors

  • David Gajser Inštitut za matematiko, fiziko in mehaniko

Downloads

Published

11/07/2016

How to Cite

Gajser, D. (2016). Verifying Time Complexity of Turing Machines. Informatica, 40(3). Retrieved from https://www.informatica.si/index.php/informatica/article/view/1407

Issue

Vol. 40 No. 3 (2016)

Section

Thesis summary

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.