In my Eastern APA talk last year, I argued that a genuinely random physical process should not be counted as a computation (in the interesting sense of the term). Jack Copeland disagreed.
So here in Jerusalem, I took the opportunity to ask two “great men” for their opinion. I’m happy to say that both Michael Rabin and Martin Davis appear to share my opinion. Rabin told me that a random process is not a computation because it’s not repeatable, and repeatability is a feature of computation. Davis, after resisting my question for a while (on the grounds that any actual physical process is finite and hence it’s not clear in which sense it would deserve to be called random), said he wouldn’t call a random process a computation.
Randomness and Computation
5 Comments
Comments are closed.
That makes me think of the problem of AI.
Could one say that the human organism contains random factors – which i guess entails some kind of infinity? At least the degree of infiniteness of the universe (its probably just a little infinite ^^).
And that this random factor is also a necessary component of intelligent life as we understand it…
Disclaimer: These are humble and unfinished laymans thoughts…
Considering a random process by itself, I’d agree that it is not a computation. But it strikes me as plausible that a random process could be part of a computation. Suppose there were some chain of steps in figuring something out and one of the links in the chain involved consulting a random process. Such a chain may very well implment various kinds of inductive inference.
Can I get an example of a genuinely random physical process?
A standard example is radioactive decay.
As to randomness and AI (see gorm’s comment above), Alan Turing already argued that randomness is an aspect of human intelligence.
As Pete Mandik notes, the outcomes of random steps may be used as inputs to a computation. This is behind important computational techniques, such as Monte Carlo simulations. (Of course, computers use pseudo-random processes (i.e., simulations of random processes) rather than genuinely random ones.)