Hacker News new | ask | show | jobs
by lisper 692 days ago
Nope. You're thinking about this mathematically, not algorithmically. The question is essentially to decide whether the output of a TM is all zeros or whether it will eventually output a 1. If it outputs a 1 you will know that in a finite amount of time by running the program, but if it never outputs a 1 then you can't tell that by running the program, and it's impossible in general to tell any other way because that would be tantamount to solving the halting problem.

Here is a concrete example: write a program that systematically tests all numbers for counterexamples to the Goldback conjecture. Every time a number fails to be a counterexample, output a zero, otherwise output a 1. Consider the output of that program to be a real number expressed as a binary decimal. If that number is not zero you will know in a finite amount of time, but if it is zero you will not know that until someone proves the Goldbach conjecture.
2 comments
bubblyworld 691 days ago
The order relation on computable reals is undecidable - this is well known, and the parent's argument is correct. If both x<y and x>y were decidable then you could easily decide equality too by just checking them and seeing if the answer to both was "no".

Computability theory is mathematics.

link
lisper 691 days ago
Tracing back through this thread, the term "deciable" was introduced in a very unfortunate way:

ekez: why is it impossible to decide whether x<0, x=0, or x>0 as in Example 1?

lisper: Only x=0 is undecidable. It's because you have to check an infinite number of digits past the decimal point to see if all of them are zero, and that will not halt.

teraflop: That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable.

Both lisper (me) and teraflop are correct. The problem is that inequality is not decidable, it's semi-decidable. It's teraflop who introduced the word "decidable" into the discussion, not me, but I didn't pay enough attention to that at that time.

/u/scarmig got it right in this comment: https://news.ycombinator.com/item?id=41150519

link
bubblyworld 691 days ago
Right, I agree that they are semidecidable, thanks for clarifying. My interpretation of "only x=0 is undecidable" was that you were claiming the other two were decidable (which is a reasonable reading imo). But it sounds like we don't actually disagree here.
link
lisper 691 days ago
It's my fault for not being more explicit. I just didn't think it all the way through.
link
teraflop 692 days ago
> Nope. You're thinking about this mathematically, not algorithmically.

I don't know what you mean by this, and I'm not sure how it relates to what I said. I'm using "decidable" in the strict, computer-science sense of the word.

The statement in example 1 of the paper, which we're discussing, is about computable real numbers. A computable real number is one for which there is a Turing machine that can calculate it to any desired finite precision in finite time.

A semidecidable problem is one for which there is a program that halts if the answer is "yes", but may not halt if the answer is "no". The halting problem is in this category.

Given a computable real number x, asking whether x<0 or x>0 are semidecidable but not decidable problems.

link
lisper 691 days ago
Yes, you're right. See https://news.ycombinator.com/item?id=41154273 for my post-mortem.
link