Jump to content

time hierarchy theorem

From Wiktionary, the free dictionary

English

[edit]

Noun

[edit]

time hierarchy theorem

  1. (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"