3 ms·
The more tractable problem is {halt, loop, unknown}. That problem us trivially solvable, and solved by every static analysis tool and optimizing compiler. Or at
by gizmo686 3y ago
The more tractable problem is {halt, loop, unknown}. That problem us trivially solvable, and solved by every static analysis tool and optimizing compiler. Or at least, the generalized {yes, no, maybe} problem for various properties is.
The real question is, how small can you make the set of instances that results in "maybe", and how small can you make the intersection of that set, and the set of instances we actually care about.
And, it turns out, you can typically make that intersection pretty small.
Regarding the question as you stated it. If you define "paradox" as whatever situation your algorithm cannot handle, then it us trivial. If you define "paradox" as the smallest possible set of "maybe", then determining what instances belong in paradox is equivalent to solving the halting problem.
- bionhoward 3y agoI would define paradox specifically as the case involved in the proof of the 2-undecidability halting problem, namely, functions of this kind: def do_opposite(): if is_halting(do_opposite): loop_forever() That's the paradox function which allegedly proves it's not worth attempting to decide {halt, loop} and so that (and other functions with the same behavior) would belong in the paradox category.