4 ms·
For it to be a DAG you'd have the solve the halting program wouldn't you?
by tick_tock_tick 4y ago
For it to be a DAG you'd have the solve the halting program wouldn't you?
- remram 4y agoNo. Knowing whether programs end in finite time (dependent on input) doesn't mean all programs end or that all programs end in constant time. The halting problem is also not considered unsolved (though P=NP is unsolved).