Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts.
From their comment:
> Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed.
You can have an arbitrarily small bias, at the cost of increased runtime — but you can’t have a zero bias algorithm that always terminates. You have to move the goalposts (allowing some bias or exceedingly rare cases to not terminate).
I’m not sure why people have such a hard time admitting that.
I don't think the termination thing is moving the goalposts.
If you have infinite time, then you can wait for it to take more than a few hundred iterations.
If you don't have infinite time, it won't take more than a few hundred iterations.
Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.
> If you have infinite time, then you can wait for it to take more than a few hundred iterations.
To be clear, you're making this argument while also arguing "this wouldn't happen in the real world". [1] You can't have it both ways.
> Also "constant time" wasn't even part of the original promise!
We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than unbounded!
A simulator that can't even promise to get to step #2 of the simulation in any bounded amount of time very much needs a giant proactive asterisk on its labeling, because that's not what people understand to be a simulator. Again, if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back.
I addressed that in my next sentence! The whole point of making it two sentences was to split up the real world and not real world cases. Come on.
> We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than this!
N is 1. Every bound is a constant bound.
> if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back.
They would not be entitled to a penny back because it's impossible for them to hit the failure case.
Even if they could hit it, nobody is getting a refund for "it crashes once per googolplex runs".
> I addressed that in my next sentence! The whole point of making it two sentences was to split up the real world and not real world cases. Come on.
Your next sentence was just obviously flat-out wrong though. Not just because who says that's the case (maybe I don't have that much time?) but because it's trivial to find P(H) that makes it false for any duration of time. "A few hundred iterations" literally doesn't guarantee anything unless you make unstated assumptions about the biases your device works for.
I don't get why we're going in circles here. It seems we've hashed everything out.
> N is 1. Every bound is a constant bound.
Kind of a meaningless statement when you don't even say what your N is. I can imagine lots of N where that's not the case. But whatever you want to call it, my point entirely stands.
> They would not be entitled to a penny back because it's impossible for them to hit the failure case.
No, it is very possible. All they need to be given is a coin whose bias they don't know beforehand, whose bias is unfortunate. Or a coin whose bias they do know to be much worse than whatever you imagined a few hundred tosses would be enough for.
> because it's trivial to find P(H) that makes it false
As I already said in the comments you read, it's proportional to the bias. A few hundred multiplied by the ratio between heads and tails or vice versa will never be reached.
> when you don't even say what your N is
Number of outputs?
Look, if you want to invoke concepts like exponential time then you tell me what N is. Exponential of what?
> All they need to be given is a coin whose bias they don't know beforehand
See first answer.
If someone expects the bias to not matter, even a one in a million coin, they're the one with the problem, not the algorithm.
If they accept the bias affects speed, things are fine.
From their comment:
> Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed.
You can have an arbitrarily small bias, at the cost of increased runtime — but you can’t have a zero bias algorithm that always terminates. You have to move the goalposts (allowing some bias or exceedingly rare cases to not terminate).
I’m not sure why people have such a hard time admitting that.