-2
$\begingroup$

The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The class of all problems solvable in polynomial time on this particular hyper computer. This would include the halting problem. Would HP = NP or(HP ⊇ NP)? As a stronger version of this, would HP = RE? and/or CO-RE?

$\endgroup$
1
  • 1
    $\begingroup$ Why did people down-vote this? Sorry if this is a tautology of some sort, but I want to learn this and couldn't find anything on the internet about it. I guess this could be reduced to asking if P^RE ⊃ NP, but this takes more then 1 operation. I don't know though. $\endgroup$ Dec 13 '21 at 17:24
1
$\begingroup$

Assume a polynomial-time Halting Decider $H$ such that given the input string $\langle M, s \rangle$ it accepts if $M$ run on string $s$ halts in finite time, rejects otherwise, and completes this computation in polynomial time.

Let $L$ be any decision problem in $NP$. Let $M$ be a Turing Machine that decides $L$. Let $M'$ be a new Turing Machine modified such that if $M$ rejects an input string $s$, $M'$ will loop forever on an input string $s$.

Now $H(\langle M', s \rangle)$ decides $L$ in polynomial time, hence all decidable problems would be in $P$. As a result, given a polynomial-time solution to the Halting Problem, $NP = P$.

$\endgroup$
7
  • $\begingroup$ "Assume a polynomial-time Halting Decider 𝐻" It seems akin to making the assumption 1 + 1 = 3 ... right? Or am I missing something? This contradicts the Halting Problem being undecidable. Why start from a false assumption? It leads nowhere, or rather everywhere. $\endgroup$
    – Michel
    Dec 13 '21 at 9:20
  • $\begingroup$ @Michel Yes, but OP's question is about the implications of that very premise: "hypercomputer capable of computing the halting problem in polynomial time". And yes, it creates the result of everything being $P$, which further illustrates why it can't really be. $\endgroup$
    – kviiri
    Dec 13 '21 at 9:41
  • $\begingroup$ I understand the argument you present (in terms of deriving the implication). From the point of view of logic though, once you start with false F, the logical implication F => S is always true. So though your statement has the form of a logical deduction, the point is that you might have saved working out the inference since the argument starts with a false hypothesis. So just replace S with any conclusion and it automatically holds. $\endgroup$
    – Michel
    Dec 13 '21 at 12:12
  • 1
    $\begingroup$ @Michel This sort of analysis is nothing unusual in theoretical CS. Oracle machines are commonly used to explore computational contrafactuals. $\endgroup$
    – kviiri
    Dec 13 '21 at 13:47
  • $\begingroup$ Sure oracles are no issue but are you not assuming an oracle that gives false info? I may be missing something. It must be that you are assuming that an oracle provides something that breaks the laws of computation and see what you can infer from that? You are assuming an oracle that provides an answer to the halting problem in P time. So it is not a Turing computable function. What theoretical cs purpose does the oracle serve? It seems you land in non CS territory, purely a mathematical construct so theory, yes, but without CS? $\endgroup$
    – Michel
    Dec 13 '21 at 14:08
1
$\begingroup$

Since the halting problem is not computable, your hyper computer would be in violation of the laws of mathematics, and therefore capable of doing anything.

$\endgroup$
6
  • 1
    $\begingroup$ incorrect. Its extremely hypothetical but it IS mathematically possible. A hyper computer can solve the halting problem for turing machines but cannot solve the halting problem for itself. Therefore it isn't contradictory. en.wikipedia.org/wiki/Hypercomputation Some models don't even require infinite steps and some might be physically possible. $\endgroup$ Dec 13 '21 at 5:10
  • $\begingroup$ Using oracles means you are changing the goal posts. The wikipedia article ends with: "Martin Davis, in his writings on hypercomputation refers to this subject as "a myth" and offers counter-arguments to the physical realizability of hypercomputation. As for its theory, ... in his argument, he makes a remark that all of hypercomputation is little more than: "if non-computable inputs are permitted, then non-computable outputs are attainable." $\endgroup$
    – Michel
    Dec 13 '21 at 6:24
  • $\begingroup$ "but it IS mathematically possible". The question is whether it is computationally possible. I am wary of "usines à gaz" in science. $\endgroup$
    – Michel
    Dec 13 '21 at 7:16
  • 1
    $\begingroup$ Its undecidable on a Turing machine. This is a hypothetical model of computation that is stronger. Just because 1 guy says its impossible doesn't necessarily mean it is. Even if its not physically possible there is nothing wrong with it mathematically. $\endgroup$ Dec 13 '21 at 16:23
  • 1
    $\begingroup$ I think you guys are misunderstanding me. Just going to clarify. A general halting decider is impossible on a Turing machine, but it isn't necessarily so on something more powerful then a Turing machine. $\endgroup$ Dec 13 '21 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.