new | ask | show | jobs
dizzant 12 days ago  [ - ]

Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?

anon48293 12 days ago  [ - ]

No. Because for let’s say the halting problem the general case says it’s unsolvable, but each specific case is solvable.

pron 11 days ago  [ - ]

1. Not all specific cases are solvable.

2. That the worst-case is very hard usually tells you that many instances will be hard (unless you discover an easy subclass), as is the case here. And when many "natural" instances are easy, that means that the problem is more interesting than perhaps previously thought, and it requires and receives more research, not less. If most instances are near the worst case, it means you know all there is to know about the problem; when they're not, it means there's more to study.

anon48293 10 days ago  [ - ]

Can you give a specific finite program which is undecidable?

pron 9 days ago  [ - ]

A program that enumerates all theorems in ZFC and stops when it proves a contradiction (e.g. true = false). Encoding a program that is equivalent to that directly as a Turing Machine in merely 748 states: https://www.scottaaronson.com/papers/bb.pdf (meaning that we cannot prove an upper bound on the 748th Busy-Beaver number, but there are probably even smaller undecidable TMs).

But my favourite example (shown here in Java) demonstrates the difficulty of analysing simple, realistic programs without necessarily being undecidable:

    long foo(long x) {
        if (x <= 2 || (x & 1) != 0)
            return 0;
        for (var i = x; i > 0; i--)
            if (bar(i) && bar(x - i))
                return i;
        throw new Error();
    }
    
    boolean bar(long x) {
        for (var i = x - 1; i >= 2; i--)
            for (var s = x; s >= 0; s -= i)
                if (s == 0)
                    return false;
        return true;
    }
Even in this case where even the input space is finite (and so everything here is definitely decidable), we simply don't yet know whether there is some x for which foo(x) throws, let alone if we made the input unbounded by using BigInteger instead of long.
jibal 12 days ago  [ - ]

Yes I disagree, because the algorithm to solve every problem takes longer to run than the remaining age of the universe.