Monday, June 12, 2006

Randomness and Computation

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.


Anonymous Anonymous said...

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

8:53 AM  
Anonymous Anonymous said...

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.

6:25 AM  
Anonymous Anonymous said...

Can I get an example of a genuinely random physical process?

12:26 AM  
Blogger gualtiero piccinini said...

A standard example is radioactive decay.

6:39 AM  
Blogger gualtiero piccinini said...

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

6:43 AM  
Anonymous Anonymous said...

Hi... (nice topic)

How shall I understand "random"...? For example, consider:
Step 1. Go to the icecream store
Step 2. See if there are vanilla and chocolate flavours in the fridge of the store.
Step 3. If there are both flavours, then flip a coin.
3.1 If side A, then Vanilla
3.2 If side B, then Chocolate
Step 4. Pay the icecream
Step 5. Come home and enjoy it! (wich could be "... come home and eat it" to avoid some critics about the experiencing of pleasure and machines)
what would a computation of this proces be? Random? Semi-random? Deeply still mechanical?

(nice blog!)

8:22 PM  
Blogger gualtiero piccinini said...

As far as I can tell, everything in your procedure is deterministic (though it may be unpredictable). In other words, there is nothing genuinely random in it.

You might want to look at the blog's new website, at

2:00 PM  

Post a Comment

<< Home