All reports by Author David Gajser:

__
TR15-036
| 17th February 2015
__

David Gajser#### Verifying whether One-Tape Turing Machines Run in Linear Time

David Gajser

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... more >>>