Turing-equivalent is usually used to mean that one system is at least as powerful as some sort of TM or UTM. Your computer is some sort of TM or UTM, and it exists inside the universe, so the universe (or its laws, rather) is quite obviously Turing-equivalent. That’s the trivial observation.
Sometimes Turing-equivalent is said to be true only if a system can both implement some sort of TM or UTM within itself, and if it can also be implemented within some sort of TM or UTM. This is a little more objectionable and not trivial, but so far I haven’t seen anyone demolish the various ‘digital physics’ proposals or the Church-Turing surmise by pointing out some natural process which is incomputable (except perhaps the general area of consciousness, but if you’re on Less Wrong you probably accept the Strong AI thesis already).
Thanks for the reply. I want to follow a related issue now.
So are all natural processes computable (as far as we know)?
I want to know whether the question above makes sense, as well as its answer (if it does make sense).
I have trouble interpreting the question because I understand computability to be about effectively enumerating subsets of the natural numbers, but I don’t find the correspondence between numbers and nature trivial. I believe there is a correspondence, but I don’t understand how correspondence works. Is there something I should read or think about to ease my confusion? (I hope it’s not impenetrable nonsense to both believe something and not know what it means.)
I have trouble interpreting the question because I understand computability to be about effectively enumerating subsets of the natural numbers, but I don’t find the correspondence between numbers and nature trivial. I believe there is a correspondence, but I don’t understand how correspondence works. Is there something I should read or think about to ease my confusion? (I hope it’s not impenetrable nonsense to both believe something and not know what it means.)
A hard question. I know no good solid answer; people have tried to explain ‘why couldn’t that rock over there be processing a mind under the right representation?’ It’s one of those obscene questions—we know when a physics model is simulating nature, and when a computation is doing nothing like simulating nature, but we have no universally accepted criterion. Eliezer has written some entries on this topic, though I don’t have them to hand.
“The laws of physics the universe runs on are provably Turing-equivalent.”
Are there any links or references for this? That sounds like fascinating reading.
It’s a trivial observation based on a constructive proof ie. that which I’m writing and you’re reading on.
(There is the issue of resource consumption, but then we have the result that the universe is Turing-complete for anything small enough.)
I don’t quite see the trivial observation yet—can you explain a little further?
Turing-equivalent is usually used to mean that one system is at least as powerful as some sort of TM or UTM. Your computer is some sort of TM or UTM, and it exists inside the universe, so the universe (or its laws, rather) is quite obviously Turing-equivalent. That’s the trivial observation.
Sometimes Turing-equivalent is said to be true only if a system can both implement some sort of TM or UTM within itself, and if it can also be implemented within some sort of TM or UTM. This is a little more objectionable and not trivial, but so far I haven’t seen anyone demolish the various ‘digital physics’ proposals or the Church-Turing surmise by pointing out some natural process which is incomputable (except perhaps the general area of consciousness, but if you’re on Less Wrong you probably accept the Strong AI thesis already).
Thanks for the reply. I want to follow a related issue now.
So are all natural processes computable (as far as we know)?
I want to know whether the question above makes sense, as well as its answer (if it does make sense).
I have trouble interpreting the question because I understand computability to be about effectively enumerating subsets of the natural numbers, but I don’t find the correspondence between numbers and nature trivial. I believe there is a correspondence, but I don’t understand how correspondence works. Is there something I should read or think about to ease my confusion? (I hope it’s not impenetrable nonsense to both believe something and not know what it means.)
A hard question. I know no good solid answer; people have tried to explain ‘why couldn’t that rock over there be processing a mind under the right representation?’ It’s one of those obscene questions—we know when a physics model is simulating nature, and when a computation is doing nothing like simulating nature, but we have no universally accepted criterion. Eliezer has written some entries on this topic, though I don’t have them to hand.