3 ms·

I'm confused. Why is the output infinite? Do we know when the hashing was stopped? I'm not sure this is a decidable problem with just the information you gave.

by GuiA 13y ago

I'm confused. Why is the output infinite? Do we know when the hashing was stopped? I'm not sure this is a decidable problem with just the information you gave. Did you just make up the problem, or is that inspired from a real world situation?

xjtian 13y ago
The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.