Are all universes Turingcomplete?
Moderators: gmalivuk, Moderators General, Prelates
Are all universes Turingcomplete?
Following the analogy that the universe is essentially an automaton, it can easily be shown that we live in a Turingcomplete universe, because we are able to implement Turingcomplete 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 borderline 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.
I know this may be only borderline 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.
 kernelpanic
 Posts: 891
 Joined: Tue Oct 28, 2008 1:26 am UTC
 Location: 1.6180339x10^18 attoparsecs from Earth
Re: Are all universes Turingcomplete?
I think that that is inherently unprovable. The Multiverse concept as well, but the Turingcompleteness more so. But if I had to vote, I'd go with nonTC 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!
 skeptical scientist
 closedminded spiritualist
 Posts: 6139
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Are all universes Turingcomplete?
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.
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
"With math, all things are possible." —Rebecca Watson
 BlackSails
 Posts: 5305
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Are all universes Turingcomplete?
Yeah, in our universe, the halting problem is trvial.
ALL turing machines halt eventually.
ALL turing machines halt eventually.
Re: Are all universes Turingcomplete?
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
 Bernard Woolley in Yes, Prime Minister
Re: Are all universes Turingcomplete?
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 nonmemory part. The nonmemory part could even be growing in space, relative to the memory part, while still leaving an infinite amount of memory.

 Posts: 69
 Joined: Sat Nov 21, 2009 5:31 pm UTC
Re: Are all universes Turingcomplete?
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.
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.
Re: Are all universes Turingcomplete?
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
 Bernard Woolley in Yes, Prime Minister

 Posts: 69
 Joined: Sat Nov 21, 2009 5:31 pm UTC
Re: Are all universes Turingcomplete?
How come? Without evidence, why restrict yourself to the less general case when describing the universe?While there is no proof either way, most scientists and philosophers agree that the universe is, in fact, discrete, and not analog.
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.
Re: Are all universes Turingcomplete?
MadRocketSci2 wrote:How come? Without evidence, why restrict yourself to the less general case when describing the universe?While there is no proof either way, most scientists and philosophers agree that the universe is, in fact, discrete, and not analog.
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.
 BlackSails
 Posts: 5305
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Are all universes Turingcomplete?
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.
 Marbas
 Posts: 1169
 Joined: Mon Jun 04, 2007 4:01 am UTC
 Location: Down down down at the bottom of the sea
 Contact:
Re: Are all universes Turingcomplete?
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?
 skeptical scientist
 closedminded spiritualist
 Posts: 6139
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Are all universes Turingcomplete?
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
"With math, all things are possible." —Rebecca Watson
Re: Are all universes Turingcomplete?
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.
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
 Bernard Woolley in Yes, Prime Minister
 thoughtfully
 Posts: 2228
 Joined: Thu Nov 01, 2007 12:25 am UTC
 Location: Minneapolis, MN
 Contact:
Re: Are all universes Turingcomplete?
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.
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.
 BlackSails
 Posts: 5305
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Are all universes Turingcomplete?
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.
 Xanthir
 My HERO!!!
 Posts: 4862
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Are all universes Turingcomplete?
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)))
 BlackSails
 Posts: 5305
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Are all universes Turingcomplete?
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.
 Xanthir
 My HERO!!!
 Posts: 4862
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Are all universes Turingcomplete?
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)))
 BlackSails
 Posts: 5305
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Are all universes Turingcomplete?
My point was that there is no evidence that spacetime itself is quantized, not that it is impossible for it to be so.
 Xanthir
 My HERO!!!
 Posts: 4862
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Are all universes Turingcomplete?
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)))
Who is online
Users browsing this forum: No registered users and 3 guests