2 ms·
> I think this is because optimization is likely an NP Optimization of computer programs is a fundamentally uncomputable affair due to Rice's theorem – in the
by IsTom 1y ago
> I think this is because optimization is likely an NP
Optimization of computer programs is a fundamentally uncomputable affair due to Rice's theorem – in the general case you can't check if two programs are equivalent.
- someguyorother 1y agoUsers of practical software would probably not accept the program taking forever, so you could implement a runtime constraint. With a runtime constraint, every TM effectively halts, so making nontrivial observations about them should at least be computable. Not that it would be easy.