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

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