time hierarchy theorem
Jump to navigation
Jump to search
English
[edit]Noun
[edit]- (mathematics, computer science) A theorem that demonstrates that allowing Turing machines additional computation time strictly increases the class of languages that they can decide.