...

I wonder if Jesus can create a number so large he can't factor it?

This is a trope on the old question of whether an all powerful God could make something so big that even he couldn't move it. I.e Church/Rosser before they "conceived" of that theorem. The question is whether there is any strict bounds on the complexity of making rocks and moving rocks. I would think that making and moving rocks is in the same complexity class. The effort to make a rock is undoubtably linearly related to the size of the rock. At least in the asymptotic case. Here's an algorithm that proves it's linear. Make a small rock. Repeat until the size is big enough. Gravity will pull it together once the rock is big enough. So this proves that the cost is at least asymptotically linear. The effort to move a rock is also linearly related to the mass of the rock. F=ma. So we can see that these are in the same complexity class. That means we can't really be sure whether he could make some rock that was slightly bigger than he could move. The complexity theory really isn't strong enough to solve it. On the other hand, creating composite numbers with two large, relatively equally sized prime factors is pretty easy to do in time linear to the number of bits. Factoring that number still requires time _exponentially_ proportional to the number of bits. So if the God had a finite amount of effort available, (but still beyond the ken of mere mortals) then I think it is safe to say that he COULD create numbers so big that even he couldn't factor them. Now what if God had a _countable_ amount of effort available? Then he should be able to factor any number that he created. I think that this follows from the same proof that shows that the rational numbers are countable. --Peter "I would build my Church/Rosser on this Rock" Wayner {I keep trying to stop making this pun, but it keeps pulling me back in.}