Blum 1967: for every total computable function r there exists a computable set A such that every TM M_i computing A admits another TM M_j computing A whose running time is r-faster almost everywhere: t_j(n) ≤ r(t_i(n)) for all but finitely…
Blum 1967: for every total computable function r there exists a computable set A such that every TM M_i computing A admits another TM M_j computing A whose running time is r-faster almost everywhere: t_j(n) ≤ r(t_i(n)) for all but finitely…