New answers tagged

4

Your function is well-defined, that is, total. The value of $f(n)$ is the maximum of the finite set $\{g_1(n), \ldots, g_{w(n)}(n)\}$. The maximum of a finite set of numbers always exists. Your function is computable iff $w$ is bounded. Suppose first that $w$ is not bounded, and assume for the sake of contradiction that $f$ were computable. Then $h(n) = f(n) ...


2

Given your comments that the numbers involved here are all fairly small, I recommend you use a SAT solver. There is a straightforward encoding: introduce boolean variables $x_{i,\ell}$, with the intended meaning that $x_{i,\ell}$ is true iff $\ell \in A_i$. Then all of your constraints can be translated into CNF clauses, and you can search for a satisfying ...


Top 50 recent answers are included