Given a set that is infinite but still countable, does a TM exist that goes over every element in the set and finds the maximum? Is this a computable function?

  • 2
    $\begingroup$ How is the set specified? The standard Turing machine can only take inputs of finite length. $\endgroup$
    – zyl1024
    Jan 13 at 3:57
  • $\begingroup$ the set is an enumeration of all total computable functions, so it is infinite but still countable $\endgroup$
    – Joey
    Jan 13 at 4:08
  • $\begingroup$ Over what domain is the set? I.e, is it a set of natural numbers? Of real numbers? Complex numbers? $\endgroup$
    – nir shahar
    Jan 13 at 10:48
  • 1
    $\begingroup$ There is no maximum in an infinite set of natural numbers. Computing the supremum (which always exists) is trivially easy in this case: always output $\infty$. $\endgroup$
    – nir shahar
    Jan 13 at 10:51

Typically, no, this is not possible. It depends on how the infinite set is represented. (I'm assuming it's a set of integers.)

The usual way to represent a possibly-infinite set $S$ is as a Turing machine $M$: $M$ enumerates all the elements of $S$. For this representation, it is uncomputable to determine the maximum element of $S$. That is, on input $\langle M \rangle$, determining the maximum element enumerated by $M$ is uncomputable. This can be proven using Rice's theorem.

There are other ways to represent possibly-infinite sets, though. The most common is using logical formulas. If the set $S$ is given by a formula $\varphi$ in some logic $\mathcal{L}$ where $S = \{w : \varphi(w)\}$, then determining the maximum element of the set $S$ may be computable if the logic $\mathcal{L}$ is simple enough. For example, if $\mathcal{L}$ is linear arithmetic (basically only addition, "and", "or", "not", $<$, and $=$), then determining the maximum is computable (returning $\infty$ if there is no maximum). But if $\mathcal{L}$ also has multiplication, then it's uncomputable.

  • $\begingroup$ A Turing Machine can encode also finite sets. And anyways, and infinite set over the integers doesn't have a maximum - so its trivially easy to compute (output $\infty$ immediately) $\endgroup$
    – nir shahar
    Jan 13 at 10:47
  • $\begingroup$ @nirshahar I changed it to "integers" and "possibly infinite" which is what I had in mind. Your statement is technically incorrect but I assume you mean "over the positive integers". $\endgroup$
    – 6005
    Jan 13 at 13:56
  • $\begingroup$ Thanks for the corrections, let me know if you notice anything wrong in the answer now. $\endgroup$
    – 6005
    Jan 13 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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