# David Gajser: Verifying time complexity of Turing machines

Date: 23. 4. 2012

Source: Graph theory and algorithms seminar

Source: Graph theory and algorithms seminar

Četrtek 26. 4. 2012 ob 12:15 v predavalnici 3.05 na Jadranski 21

Two people, Andrej and Tomaž, have their own one-tape
Turing machine. Andrej asserts, that his TM runs in time A(n) and
Tomaž asserts that his TM runs in time T(n). Suppose A(n)=o(n log(n))
and T(n)=\Omega(n log(n)). We claim that Tomaž is able to verify
Andrej's assertion, but Andrej has no algorithm to verify the assertion
of Tomaž.