time hierarchy theorem

English edit

Noun edit

time hierarchy theorem

(mathematics, computer science) A theorem that demonstrates that allowing Turing machines additional computation time strictly increases the class of languages that they can decide.

Retrieved from "https://en.wiktionary.org/w/index.php?title=time_hierarchy_theorem&oldid=77763740"