Hacker News Reader

Comment by abductee_hg | Hacker News Reader

wait, does that mean that Rice's theorem is wrong and machines can now solve nontrivial semantic problems?

No. One of the authors talked about this point - among others - here: https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/

"MIP* = RE shows that, with quantum entanglement, there can be a chasm of computability between verifying solutions and finding them."

No, from my reading, this uses the opposite, it uses the fact that the halting problem is unsolvable to show that MIP* cannot solve harder problems than RE, which are a class easier than nontrivial semantic questions and the halting problem.

I think you are mistaken. RE is the class that includes the halting problem.

I know its really bad form to complain about downvotes - but can i ask if people are disagreeing with me or if there is something else objectionable in my comment? If its the former, i'm confused as its trivially easy to google the definition of recursively enumerable, if its the latter I am honestly curious.

The halting problem is RE complete, which means it's both RE Hard (every problem in RE can be reduced to the halting problem) and in RE.

It does seem from the article that they use an argument that the halting problem is unsolvable to somehow give an upper bound on complexity, but I wonder if the paper really does that.

"the fact that the halting problem is unsolvable" This is less of a fact and more of a conjecture. As always in mathematics we use implicit context and sometimes that context gets lost to a damaging degree. The whole, and true, sentence would be "the fact that the halting problem is unsolvable by a turing machine and, given that the Church Turing thesis is true, unsolvable in general".

It would be a pitty if the paper simply assumes the Church Turing thesis as true, because if we ever find a hypercomputation counterexample to the CTT, it'll probably come from a place like quantum computing and physics, where there might be more reals than the computable reals, where the axiom of choice could work, and where infinity might be a reified thing instead of a process.

> Rice's theorem

Is it even a theorem, such hand-wavy thing is a theorem boggles my mind.

I'm curious how you find it to be hand-wavy? I only vaguely recall the details of Rice's Theorem and its proof from University years ago, but does it not stand on some very rigorous formal foundation?

In fact, computability theory sometimes strikes me as one of the most rigorous fields, and aren't all of the hand-wavy sounding words in Wikipedia's first paragraphs of Rice's Theorem for example, in reality very rigorously defined as well?

> Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

Are people okay with the word "non-trivial" ? Is it even quantifiable?

We call a property non-trivial if there is a computable (partial) function that satisfies the property and another computable (partial) function that doesn't satisfy the property.

E.g. "returns 4 for some input" is a non-trivial property: the function 'f(x) = 4' satisfies it, while the function 'f(x) = 7' does not.

Non-trivial here means something specific (see the other reply), people say "non-trivial" in this context as an abbreviation of what it means, it's not a vague term that readers are asked to give an interpretation to.

Even the introductory paragraph on Wikipedia that I mentioned immediately defines it for the context: “A property is non-trivial if it is neither true for every computable function, nor false for every computable function.” I think that’s as rigorous as can be. (You’d have to look up the actual definition of “property”, “computable”, and “function” of course. “True” and “false” are probably obvious, however.)

Reply on news.ycombinator.com