David Gajser: Verifying time complexity of Turing machines
Datum objave: 23. 4. 2012
Seminar za teorijo grafov in algoritme
Č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ž.