Verifying Time Complexity of Turing Machines

David Gajser

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?

Full Text:

PDF

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.




Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.