1
$\begingroup$

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem:

Is there a maximal decidable set of terminating programs?

A set is maximal if it is not the subset of another such set. A program may be a Turing Machine or an equivalent model.

I came up with a simple argument to prove that such a maximal set cannot exist: We can take an arbitrary terminating program that is not yet in the set and add it, the result would still be decidable. The only candidate left for the maximal set is the set of all terminating programs which is however not decidable.

I am not completely convinced by my own argument though and it does not seem to give me any insight into the problem. Is it correct? Is there a more satisfying explanation? Can the problem be formulated differently to make it more meaningful, maybe ignoring the case that finitely many problems can always be added?

Furthermore, I think an equivalent, more practical formulation of the question I have in mind is whether there is an "optimal" termination decider (cannot detect more terminating programs). The implications confuse me. If it does not exist, does that mean any such decider program can always be improved?

$\endgroup$
1
  • $\begingroup$ Your argument is correct. Sounds perfectly satisfying too. $\endgroup$
    – Dmitry
    Commented Mar 29, 2023 at 23:26

1 Answer 1

1
$\begingroup$

Your proof is correct. There is no maximal decidable set. Yes, your conclusion is right, there is no optimal termination decider, as you can always come up with another one that detects one more terminating program. It's like noting that there is no largest number: for any number you name, I can always name one that is bigger.

$\endgroup$
2
  • $\begingroup$ There is no maximal decidable set. Each program either terminates or doesn't terminate, so there is a set of all programs that don't terminate - we just don't know which ones those are. $\endgroup$ Commented Mar 30, 2023 at 6:38
  • $\begingroup$ @user253751, good point, thank you for the correction. I have revised my answer accordingly. $\endgroup$
    – D.W.
    Commented Mar 30, 2023 at 21:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.