Computer scientists do know the halting problem, which in general boils down to this: when looking at a computer program and a given input set the question is if this program runs forever or will come to a halt eventually.
For example this pseudo code runs forever:
while this program terminates:
For simple programs and input sets the questions can be easiliy solved; the more complex the data though gets the harder it gets to give an answer.
This problem was being first postulated by Kurt Gödel (incompleteness theorems) and Alan Turing proved that it is impossible to create an algorithm on a Turing machine which is able to compute an answer to this problem.
So this is something of a hard border for computer sciences and one of its classic problems/proofs, well... until now maybe. Computer scientists created as thought experiment a hypothetical new proof system called
MIP, where a regular computer asks questions to a pair of all-knowing but not necessarily honest “oracles” that cannot communicate with one another.
In reality the problem would be to build such a "all-knowing oracle", which might be impossible to do so. But since this is theory we can already pretend that such things do exist and work with them, also determine their power; even better, we could entangle those oracles on quantum level and call that thing MIP*, which is an improved version of this proof system.
Last year, Wright and Natarajan drafted a proof showing that the spooky connection in the MIP* class gives the verifier interrogating the entangled provers the power to check even more difficult problems (those whose complexity increases double-exponentially with the size of the input). The added entanglement gives more knowledge to the verifier to ask better questions of the provers (the oracles).
And on top of that this construction would be even more powerful than originally thought:
They posit that MIP* could efficiently verify every problem in the “recursively enumerable class,” or RE, basically every problem for which it would take a finite amount of time to calculate if the answer was “yes;” a “no” answer could take an infinite amount of time to calculate. MIP*=RE.
The halting problem is part of the RE class. So this means,
if this research including its proof is to be found correct, that in theory it is possible to build a machine which is being able to compute the halting problem reliable in fast time. Which by the way would not invalidate Turing's findings, because he worked on a different theoretical construction for his proof, it would just mean that in theory there could be a class of machines which could to this - if we are ever being able to build them is a totally different kind of story. But quite probably we might not be able to do that.
You enter a cave. At the end of a dark corridor, you encounter a pair of sealed chambers. Inside each chamber is an all-knowing wizard. The prophecy says that with these oracles’ help, you can learn the answers to unanswerable problems. But there’s a catch: The oracles don’t always tell the...
gizmodo.com
Link to the paper:
[2001.04383] MIP*=RE