4 ms·

AFAIK cycle detection does not tell you if a program will halt, only that a program has a cycle. while(random() != 0) { wait(1second); } will this

• rocqua 4y ago
  Turing machines do not have a true random(). In general the space of deterministic and probabilistic programs are very different. Now if you were to use a pseudo-random generator, and presume that this is the only function sampling from it, then all of a sudden the halting problem for this generator is well-defined. It also becomes a very simple question about the pseudo-random generator. If the random() function is truly random, then you are talking about a machine more powerful than a turing machine.
  • gweinberg 4y ago
    It is not a simple to answer question. If you want to know whether there is a binary string that hashes to a particular value, it may be that the only way to prove that one exists is to keep testing strings until you find one that hashes to the correct value. And if it turns out that no such string exists, that may be impossible to prove. You can in principle prove that no such string below some particular finite length exists, but it could well be impossible to prove that no such string of any length exists.
    • rocqua 4y ago
      For many pseudo-random generators, it is known what their period is. For most of those, it is known that they reach all possible states. For cryptographic quality random generators, I am not sure how much is known. In any case, the question is a simple one, though answering it can be difficult in some cases.