Science Forums 2

[CraigD]

Originally Posted by phillip1882

well consider the following code

while z <100:
   y = random.randint(0,100)
   x = random.randint(0,y)
   z = random.randint(0,x)

this should halt, but it could take hours, and there wouldn't be much of a determinable pattern.

Though a bit off the topic of the halting problem, the questions raised by Phillip's example of a program that uses a random number function can shed light on some important characteristics of Turing machines.

Although a real computer can have a “true” random number function via special hardware or clever use of ordinary hardware (see the wikipedia article section ”Generating random numbers from physical processes”), none of this hardware is available to a Turing machine, which is completely deterministic. While you could write a Turing machine that generates pseudorandom numbers, or even an implementation of a python interpreter that could run the code above, given the machine and its initial tape (which would contain symbols corresponding to a specified python random.seed(x) value), it would be possible to determine the exact value of z at any point in the program’s execution, which would coincidentally also determine exactly when it would halt.

The key point I’m trying to make is that, although they can be similar enough for practically any purpose, the pseudorandom numbers that can be generated with a Turing machine are not truly random, or in principle any less deterministic than the values in the examples in Phillip’s previous post.

Assuming that true randomness exists (an uncertain philosophical and physical assumption), if the quoted program were run with the random module configured to use a true random number generator (eg: a chip that detected decay events of a radioisotope sample, not just at seed time, but continuously), when, or even whether, the program would halt would be truly impossible to determine, as a small but non-zero probability of it running for an arbitrarily long time would exist.