Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

Question

I need some clarification regarding if computer scientists say a program like:

$random_value = Get-Random -Maximum 100
Write-Output $random_value

while ($random_value -ne 0) {
    $random_value = Get-Random -Maximum 100
    Write-Output $random_value
}

always halts. It's PowerShell code that runs Get-Random a pseudo-random number of times, basically until Get-Random returns 0. I'm interested in this class of programs, not just this concrete example.

I truly see some ambiguity about whether we can say these types of programs always halt. If they don't always halt (because maybe one execution is so lucky to never land on 0), then this seems to make the Halting Problem incredibly basic, almost too basic (not that that's necessarily a bad thing). Like, of course the Halting Problem must be true based off this example, just show this in every intro CS class (then why didn't my professor?). If they do always halt (because let's face it, this program will halt in some finite time based on probability), then I guess I need to get used to this lingo that computer scientists seem to make more natural sense of than I do.

To me, taker of a single CS class so far, we would need to run it to see if it halts, and that's the only way. No other program could tell. Because technically it could run forever if the hardware didn't fail.

Maybe the pseudo-random nature of Get-Random makes this always halt in a more clear cut manner. Then I'll just have to ask about non-pseudo-random random() functions.

Answer 1

The Halting Problem is defined on deterministic Turing machines, which do not have randomness.

There is a probabilistic version of the Halting Problem for probabilistic Turing machines, which asks if a program halts with probability at least 1/2. This problem is also known to be undecidable, see here.

Answer 2

If you are asking about pseudo random numbers, then your example is decidable: a PRNG is, by definition, not random at all, but if starting from the same seed is guaranteed to repeat exactly as before. It is also highly likely that a PRNG is guaranteed to "hit" all numbers it can hit eventually, by construction, though you would have to prove that separately. In any case it is likely that you can find an argument whether it hits all of them, or whether some numbers cannot be encountered ever (by construction), which would give you the answer to the halting problem for your concrete simple code in any case.

This can also be run on a Turing machine, as a PRNG is just regular code + data, nothing special.

If it is a true RNG the concept of the Halting Problem does not apply, as @orlp mentioned their answer (with hints on probabilistic versions), since a turing machine cannot interact with the physical world to get truly random numbers.

Of course you can just "naively" ask whether a given program halts, and in this case your problem is equivalent to figuring out whether your RNG can in fact output that number. If you find out that it cannot (many possible reasons), you have your answer. If you find that it can, but you cannot figure out whether there is a guarantee of it ever hitting that number, your "naive" halting problem cannot be answered.

Generally, the difficulty (or "baseness") of the algorithm has no impact - from the point of view of Computer Science, the Halting Problem is what it is. Nobody needs to try to implement a checker for whether some algorithm halts, because we have proof that this is generally impossible.

OP mentioned in a comment that they are interested in a simple example for an "interesting" algorithm which is hard to reason about regarding its halting or not. There is a question for that, but I find it only illustrates that it is not easy to come up with a seemingly simple problem - most answers in that question transfer an unsolved (by us) problem from maths into an algorithm. But all these examples are not "simple" by any stretch of the imagination, even if they are very short in their formulation. After all, they are all so complex that we cannot find solutions!

Wikipedia has a cheeky little non-rigorous proof which is easy to understand for me at least; this would be the one you could give your pupils (if this in the context of school/uni) or use yourself. It is hardly a "real world" algorithm, but many things in Computer Science are not...

Answer 3

Pseudo-random number generators (at least the ones I know of, and in particular this one) output a fixed cycle of numbers, with the starting point determined by the seed. So unlike true randomness, you can be certain that at one point, you will see all numbers that are at all achievable with the generator. So yes, this halts (under the assumption that 0 is part of the cycle, see comment by Trayman).