[tick_tock_tick]

For it to be a DAG you'd have the solve the halting program wouldn't you?

[remram]

No. 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).