4
I see two ways of interpreting this question, but the answer is essentially trivial either way.
Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a Turing machine?
Yes, because that is the definition of a hypercomputation model.
A caveat: Technically, you could have a hypercomputation model that (as ...
2
Trivially every computable problem is reducible to $A_{TM}$. On the other extreme, there are plenty of problems which are $A_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A_{TM}$ - for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input $0$}\}$$ is Turing-equivalent to $A_{TM}$.
A more ...
2
The study of models of computation extremely broadly construed is called "generalized recursion theory" (or "higher recursion theory," or "generalized/higher computability theory," or etc.). We can indeed rigorously define and study (from a theoretical standpoint of course) models of computation much stronger than what is "physically implementable" in even ...
1
Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:
\begin{align}
\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\
&\text{and $M$ }accepts\text{ $w$ after a finite computation}\}
\end{align}
1
Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?
I guess the answer is yes, but please check critically. One can easily construct an infinite recursive set of indices of $\phi$ (adding "comments" to a program). From this infinite recursive set one can pick out a non recursively enumerable subset.
Only top voted, non community-wiki answers of a minimum length are eligible
