# Turing machine to find maximum of an infinite set

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?

• How is the set specified? The standard Turing machine can only take inputs of finite length. Jan 13 at 3:57
• the set is an enumeration of all total computable functions, so it is infinite but still countable
– Joey
Jan 13 at 4:08
• Over what domain is the set? I.e, is it a set of natural numbers? Of real numbers? Complex numbers? Jan 13 at 10:48
• 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$. 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.

• 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) Jan 13 at 10:47
• @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".
– 6005
Jan 13 at 13:56
• Thanks for the corrections, let me know if you notice anything wrong in the answer now.
– 6005
Jan 13 at 13:57