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.
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.
posted by gualtiero piccinini at 10:54:00 AM
7 Comments:
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.)
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!)
Vic,
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 philosophyofbrains.com
Post a Comment
<< Home