Skip to main content
MathOverflow

Return to Question

typo
Source Link
François G. Dorais
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?

For example what would be the complexity class of the language of "provably halting turringTuring machines that halt in an even number of steps"

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?

For example what would be the complexity class of the language of "provably halting turring machines that halt in an even number of steps"

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?

For example what would be the complexity class of the language of "provably halting Turing machines that halt in an even number of steps"

Source Link
ken
ken
  • 11
  • 1

unbounded complexity

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?

For example what would be the complexity class of the language of "provably halting turring machines that halt in an even number of steps"