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

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 psuedo-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 psuedo-random nature of Get-Random makes this always halt in a more clear cut manner. Then I'll just have to ask about non-psuedo-random random() functions.

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.

• Yep. So to properly "show this in every intro CS class (then why didn't my professor?)" as the OP suggests, the professor would also need to show the algorithm implemented by the Get-Random routine.
– bdsl
Commented Jul 17 at 12:30

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...

• Thanks, I definitely believe in the HP's correctness, this was an example to see if the HP can be motivated/understood from a very easy to understand example. Commented Jul 17 at 17:07
• @JKusin, I see. I have added two paragraphs regarding a simple example.
– AnoE
Commented Jul 18 at 9:04

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).

• Only if 0 is a part of the cycle. Proving that it is in general (i.e. for any PRNG) is not possible, because we can't even prove that the PRNG is cyclic (due to Rice's theorem). For a cyclic PRNG we could in principle prove that 0 is or is not a part of the cycle just by running through the cycle. But this could be hard in practice since the cycle can be very long. A PRNG can be acyclic, if it's allowed growing storage. An example would be a (not so good) PRNG that generates the digits of π. Commented Jul 17 at 7:22
• @TrayMan PRNGs that allocate storage are going to be pretty slow in practice. For a PRNG that doesn't allocate, it clearly must be cyclic, which covers most PRNGs I'd believe.
– Yakk
Commented Jul 17 at 13:50
• @TrayMan So where does that leave me? Your comment makes it sounds like we really would have to run this as the only way to check for halting, given a PRNG that is not provable to be cyclic (which apparently exist) and increasing storage capacity. If I'm reading you correctly, this would motivate the halting problem and I suggest to CS educators this might be a quick and easy to way to introduce it (and I'm left wondering why I never see this type of example in the pedagogy regarding halting) Commented Jul 17 at 17:11
• @JKusin: If the PRNG is truly acyclic, it must use an unlimited amount of memory as time goes to infinity (i.e. for any fixed amount of memory X, it must eventually use more than X). So in the Real World™, such a PRNG will halt when it runs out of memory. A Theoretical Computer Scientist would say that that is irrelevant because memory limitations are not part of the standard Turing machine model, but then neither is the system time or anything else you might plausibly use as a seed value for a PRNG. Commented Jul 17 at 17:16
• @JKusin The takeaway is that often you need specific proof techniques to handle specific cases. All practical PRNGs I've seen are provably cyclic, simply because they don't allocate memory. The cycle can be too long to practically prove whether there's a 0 just by running it, but a specific PRNG might have some other way of proving that. It's important to note that the halting problem states that it's not provable in general whether an algorithm terminates. There's nothing that says you can't prove it in specific cases. In this case, provability depends on the PRNG algorithm used. Commented Jul 17 at 20:35