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) ...
1
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 $\...
1
Yes. In general - for a language $L$ an oracle to $L$ is equivalent to an oracle of $\overline L$.
Since the complement of the halting problem is co-RE complete (it is immediate from the fact that the halting is RE complete), then an oracle to it can solve all co-RE.
1
Another "cool" way to prove it is realizing that there is an immediate reduction from the Post Correspondence Problem to the problem of checking wether a CFG grammar accepts a palindrome (or equivalently checking wether 2 CFG grammars accept the same string).
Given a PCP instance; i.e. a set of tiles
$\{ (x_i / y_i) \}$ (wher $x_i$ is the top ...
1
If H(x,x) goes into an infinite loop, then that fact already proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop.
If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't ...
Only top voted, non community-wiki answers of a minimum length are eligible