3 ms·
The problem is that because it’s random there is a chance it will never complete, so the same input alternates between halting and non-halting, so the average t
by olliej 8y ago
The problem is that because it’s random there is a chance it will never complete, so the same input alternates between halting and non-halting, so the average time is infinite. Which is clearly nonsensical, hence it isn’t an algorithm.