Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be bounded in any way if the problem is undecidable.

But is there any other notion that makes sense to say that one problem is "harder" than another even though both are semi-decidable?

  • 2
    $\begingroup$ Fix your favourite notion of reduction, and say that A is harder than B if B reduces to A but A does not reduce to B. $\endgroup$ Commented Sep 13, 2023 at 19:14
  • 1
    $\begingroup$ Are you so sure time & space aren't suitable? You could still talk about the time, space, etc complexity on inputs where the machine halts. $\endgroup$ Commented Sep 13, 2023 at 20:06
  • $\begingroup$ If I found an upper bound on the time took on terminating instances, couldn’t I just wait for that time and answer on non-terminating instances as well? $\endgroup$ Commented Sep 13, 2023 at 20:43
  • 1
    $\begingroup$ Only if the upper bound is a computable function. $\endgroup$ Commented Sep 13, 2023 at 21:46
  • $\begingroup$ Interesting. Is there an example of undecidable problem where a semi-decision procedure has a non-computable upper bound on the running time for accepted instances? $\endgroup$ Commented Sep 14, 2023 at 17:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.