Are all universes Turing-complete?

For the discussion of the sciences. Physics problems, chemistry equations, biology weirdness, it all goes here.

Moderators: gmalivuk, Prelates, Moderators General

Are all universes Turing-complete?

Postby afarnen » Wed Mar 10, 2010 2:01 am UTC

Following the analogy that the universe is essentially an automaton, it can easily be shown that we live in a Turing-complete universe, because we are able to implement Turing-complete systems within its rules. My question is, must all universes in the multiverse (ones with twerked fundamental constants) necessarily have this same property? I think it's an interesting question, but maybe it's not.

I know this may be only border-line science, but I'm more interested in the multiverse than Turing completeness in asking this question, so I didn''t post it in computer science.
afarnen
 
Posts: 157
Joined: Mon May 05, 2008 12:12 pm UTC

Re: Are all universes Turing-complete?

Postby kernelpanic » Wed Mar 10, 2010 3:19 am UTC

I think that that is inherently unprovable. The Multiverse concept as well, but the Turing-completeness more so. But if I had to vote, I'd go with non-TC because it is possible that fundamental constants are such that no matter exists, and that is therefore not TC.
I'm not disorganized. My room has a high entropy.
Bhelliom wrote:Don't forget that the cat probably knows EXACTLY what it is doing is is most likely just screwing with you. You know, for CAT SCIENCE!

Image
User avatar
kernelpanic
 
Posts: 891
Joined: Tue Oct 28, 2008 1:26 am UTC
Location: 1.6180339x10^18 attoparsecs from Earth

Re: Are all universes Turing-complete?

Postby skeptical scientist » Wed Mar 10, 2010 4:07 am UTC

Well, if enough of the fundamental constants are zero, then there is no interaction between particles, so no computation is possible.

On the other hand, is this universe really Turing complete? That would require infinite space and time to do computations in, and there's no reason to believe that this is true of our universe.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Are all universes Turing-complete?

Postby BlackSails » Wed Mar 10, 2010 5:05 am UTC

Yeah, in our universe, the halting problem is trvial.

ALL turing machines halt eventually.
User avatar
BlackSails
 
Posts: 5252
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Are all universes Turing-complete?

Postby Diadem » Wed Mar 10, 2010 8:08 am UTC

Yeah our universe certainly isn't turing complete. In fact I have trouble imagining a turing complete universe. It would have to be infinite in both time and space, but more problematic it also would have to have no entropy.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister
User avatar
Diadem
 
Posts: 4950
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: Are all universes Turing-complete?

Postby Zamfir » Wed Mar 10, 2010 8:19 am UTC

Diadem wrote:Yeah our universe certainly isn't turing complete. In fact I have trouble imagining a turing complete universe. It would have to be infinite in both time and space, but more problematic it also would have to have no entropy.

Is that true? If a universe is infinite in space, you could have both an infinite amount memory and an infinite amount of other stuff. Entropy could then be transferred to the non-memory part. The non-memory part could even be growing in space, relative to the memory part, while still leaving an infinite amount of memory.
User avatar
Zamfir
 
Posts: 6345
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: Are all universes Turing-complete?

Postby MadRocketSci2 » Thu Mar 11, 2010 3:45 am UTC

Also, turing machines operate on discrete values. They are digital.

The universe may be analog. (To head off the objection: Quantum physics doesn't enforce discreetness of the state variables describing a system in the full turing sense, just that stationary states of the wavefunction happen at discrete eigenvalue intervals under some circumstances. To explain why certain things like electron orbitals are normally at discrete intervals, the underlying wave equation operates on continuous fields)

All analog functions mapping reals to reals, sets of analog differential equations, ect, are not turing computable in general exactly - only to finite precision dependent on the discretization scheme.

That's not to say that you can't have cool and meaningful things with turing machines, or digital computers. Our brains are digital, as far as I know. But you might need something more to describe the state and operation of the universe than a discrete system.
MadRocketSci2
 
Posts: 69
Joined: Sat Nov 21, 2009 5:31 pm UTC

Re: Are all universes Turing-complete?

Postby Diadem » Thu Mar 11, 2010 10:59 am UTC

MadRocketSci2 wrote:The universe may be analog.

While there is no proof either way, most scientists and philosophers agree that the universe is, in fact, discrete, and not analog.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister
User avatar
Diadem
 
Posts: 4950
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: Are all universes Turing-complete?

Postby MadRocketSci2 » Thu Mar 11, 2010 1:35 pm UTC

While there is no proof either way, most scientists and philosophers agree that the universe is, in fact, discrete, and not analog.
How come? Without evidence, why restrict yourself to the less general case when describing the universe?

Discrete, in my mind, means more than being able to decompose something into an infinite series of eigenfunctions (which isn't discrete at all, when you think about it) - it would mean there would have to be some sort of natural "pixelization" of the underlying state variables, which would crush all sorts of apparent symmetry and relativity.
MadRocketSci2
 
Posts: 69
Joined: Sat Nov 21, 2009 5:31 pm UTC

Re: Are all universes Turing-complete?

Postby Josephine » Thu Mar 11, 2010 4:36 pm UTC

MadRocketSci2 wrote:
While there is no proof either way, most scientists and philosophers agree that the universe is, in fact, discrete, and not analog.
How come? Without evidence, why restrict yourself to the less general case when describing the universe?

Discrete, in my mind, means more than being able to decompose something into an infinite series of eigenfunctions (which isn't discrete at all, when you think about it) - it would mean there would have to be some sort of natural "pixelization" of the underlying state variables, which would crush all sorts of apparent symmetry and relativity.

But there is natural pixelization. You can thank Planck for that. things moving between them in a way that would seem to be inconsistent with that are explained by things having a higher probability of being in a "planck voxel" closer to it than farther away.
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.
User avatar
Josephine
 
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: Are all universes Turing-complete?

Postby BlackSails » Thu Mar 11, 2010 8:17 pm UTC

nbonaparte wrote:But there is natural pixelization. You can thank Planck for that. things moving between them in a way that would seem to be inconsistent with that are explained by things having a higher probability of being in a "planck voxel" closer to it than farther away.

There isnt any evidence that space itself is discretized.
User avatar
BlackSails
 
Posts: 5252
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Are all universes Turing-complete?

Postby Marbas » Thu Mar 11, 2010 9:22 pm UTC

BlackSails wrote:
nbonaparte wrote:But there is natural pixelization. You can thank Planck for that. things moving between them in a way that would seem to be inconsistent with that are explained by things having a higher probability of being in a "planck voxel" closer to it than farther away.

There isnt any evidence that space itself is discretized.



So, my study of Differential Geometry isn't that thorough yet, but doesn't Differential Geometry kind of require a continuity of your curves, surfaces etc? Doesn't that mean GR requires space to not be discretized to work properly? Or is there something funny happening like, the gaps between points in space have measure zero or something, allowing integrability? Although that would probably still ruin differentiability.

Blurfderf halp.
Jahoclave wrote:Do you have any idea how much more fun the holocaust is with "Git er Done" as the catch phrase?
User avatar
Marbas
 
Posts: 1170
Joined: Mon Jun 04, 2007 4:01 am UTC
Location: Down down down at the bottom of the sea

Re: Are all universes Turing-complete?

Postby skeptical scientist » Thu Mar 11, 2010 9:29 pm UTC

Both QM and GR are mathematical models, so neither actually tells us how space really is, just that they are close enough to reality to make decent predictions. GR tells us that space looks smooth at large enough scales that GR makes reasonable predictions. QM tells us that certain things are quantized. Neither theory tells us what space really is, only how to make predictions that are largely confirmed by experiment.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Are all universes Turing-complete?

Postby Diadem » Thu Mar 11, 2010 9:50 pm UTC

Nevertheless, our best theories of the universe on the smallest scales are grainy. While that is not proof, it suggests that the universe itself may be grainy. Also this is philosophically more appealling.

So yeah, the universe is usually assumed to be discrete.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister
User avatar
Diadem
 
Posts: 4950
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: Are all universes Turing-complete?

Postby thoughtfully » Thu Mar 11, 2010 10:17 pm UTC

The Uncertainty Principle provides a "maximum resolution". This is not the same thing as spacetime being parceled up into well defined boxes. It isn't the case that you can say at time t0 particle A is somewhere in box X1,Y1,Z1 and at time t1 it's in one of
X0,Y1,Z1; X2,Y1,Z1;
X1,Y0,Z1; X1,Y2,Z1;
X1,Y1,Z2; X1,Y1,Z2.

This imposes a coordinate system. The particle can't be displaced by a Planck Length unless its along one of the axes.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery
User avatar
thoughtfully
 
Posts: 2101
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN

Re: Are all universes Turing-complete?

Postby BlackSails » Thu Mar 11, 2010 11:37 pm UTC

Diadem wrote:Nevertheless, our best theories of the universe on the smallest scales are grainy. While that is not proof, it suggests that the universe itself may be grainy. Also this is philosophically more appealling.

So yeah, the universe is usually assumed to be discrete.


No, they are blurry, not grainy.
User avatar
BlackSails
 
Posts: 5252
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Are all universes Turing-complete?

Postby Xanthir » Fri Mar 12, 2010 3:58 am UTC

BlackSails wrote:
Diadem wrote:Nevertheless, our best theories of the universe on the smallest scales are grainy. While that is not proof, it suggests that the universe itself may be grainy. Also this is philosophically more appealling.

So yeah, the universe is usually assumed to be discrete.


No, they are blurry, not grainy.

Nevertheless, there are indeed supported physical theories involving discrete spacetime.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4323
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: Are all universes Turing-complete?

Postby BlackSails » Fri Mar 12, 2010 4:12 am UTC

Xanthir wrote:
BlackSails wrote:
Diadem wrote:Nevertheless, our best theories of the universe on the smallest scales are grainy. While that is not proof, it suggests that the universe itself may be grainy. Also this is philosophically more appealling.

So yeah, the universe is usually assumed to be discrete.


No, they are blurry, not grainy.

Nevertheless, there are indeed supported physical theories involving discrete spacetime.


And there are also theories which demand continuous spacetime, such as bohm's interpretation of quantum mechanics.
User avatar
BlackSails
 
Posts: 5252
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Are all universes Turing-complete?

Postby Xanthir » Fri Mar 12, 2010 1:30 pm UTC

Sure, I'm not challenging that. I was just pointing out the fact about grainy spacetime, because some people seemed to be indicating that they thought that *no* serious theory used grainy spacetime.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4323
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: Are all universes Turing-complete?

Postby BlackSails » Fri Mar 12, 2010 4:27 pm UTC

My point was that there is no evidence that spacetime itself is quantized, not that it is impossible for it to be so.
User avatar
BlackSails
 
Posts: 5252
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Are all universes Turing-complete?

Postby Xanthir » Mon Mar 15, 2010 5:36 am UTC

I'll grant that. There's no direct evidence yet, nor indirect evidence making one of the "grainy spacetime" theories especially compelling over its competitors.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4323
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex


Return to Science

Who is online

Users browsing this forum: No registered users and 12 guests