Another example (from the real world this time): I make a progress bar for an iterative optimization of an design in a program. The number of iterations until the design completes can't be reliably estimated. It's not completely underterministic of course, but the complexity of making that estimation isn't just high, it's likely to be so high that it approaches the complexity of the optimization itself.