Hm, I wonder if I could make these students more miserable by introducing a CPU that permits static operation, then clocking that with a true random number generator?

So now it has output that is deterministic from the standpoint of the CPU but nondeterministic to an outside observer. Probably wouldn't affect the O(n) notation though, come to think of it. It would be funny though.