View Full Version : Is the universe easy to compute?
Chris Pollett
Oct25-04, 08:09 AM
<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\n\nHi,\n\nI come from a computer science/logic background and I had some questions\nthat are directed towards those who have put forward discrete\nmodels for the universe. Basically, I have some naive intuitions about\nhow such a theory would have to work and was thinking this might yield\nsome consequences about the complexity of the universe, so I was\nwondering how off-base my assumptions were?\n\nFirst, I am guessing that in these models one can extract a notion of\narc length of a position in the universe from the big bang? And the\npossible lengths come in discrete values? My impression is that all\nthese models are finite dimensional. Does this imply that that the\nnumber of possible positions with less than a given arclength l is\nbounded by l^d for some fixed d? Are the allowable possible states\nthat a given position could be in finite?\n\nAssuming the answer to the above questions are yes, then here is where I\nam going... Consider the function which maps from the points of\narclength less than or equal to l to those of length l+1. How\ncomplicated a function can this be? In particular, as both spaces\nare finite and polynomial in l, the number of such maps is finite and at\nmost double exponentially in a polynomial in l bounded. You could write\ndown an exponential in l size string S_l to describe the correct such\nmap. Presumably, to describe any possible universe from an aribitrary\nbig bang for all time we can do better\nthan write down S_1,S_2, ... S_l S_{l+1}... as going from S_l to S_{l+1}\nprobably does not vary completely nonuniformly in l. My guess is in\nthese theories evolution is governed by matrix multiplication/ operator\napplication of some kind and that people in the know could extract\nthe computational complexity of this operator? Is it p-time?\nA Turing Machine that just tried out all possible next states from the\ncurrent would run in p-space, but it wouldn\'t necessarily ``know\'\' when\nit hit the correct next state to stop. My feeling is that there should\nbe enough uniformity in physics that the answer ought to be very\nrecursive that is at most a fixed stack of exponentials, but I don\'t\nknow enough to say anything.\n\nChris\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form"> View this Usenet post in original ASCII form </a></div><P></jabberwocky>Hi,
I come from a computer science/logic background and I had some questions
that are directed towards those who have put forward discrete
models for the universe. Basically, I have some naive intuitions about
how such a theory would have to work and was thinking this might yield
some consequences about the complexity of the universe, so I was
wondering how off-base my assumptions were?
First, I am guessing that in these models one can extract a notion of
arc length of a position in the universe from the big bang? And the
possible lengths come in discrete values? My impression is that all
these models are finite dimensional. Does this imply that that the
number of possible positions with less than a given arclength l is
bounded by l^d for some fixed d? Are the allowable possible states
that a given position could be in finite?
Assuming the answer to the above questions are yes, then here is where I
am going... Consider the function which maps from the points of
arclength less than or equal to l to those of length l+1. How
complicated a function can this be? In particular, as both spaces
are finite and polynomial in l, the number of such maps is finite and at
most double exponentially in a polynomial in l bounded. You could write
down an exponential in l size string S_l to describe the correct such
map. Presumably, to describe any possible universe from an aribitrary
big bang for all time we can do better
than write down S_1,S_2, ... S_l S_{l+1}... as going from S_l to S_{l+1}
probably does not vary completely nonuniformly in l. My guess is in
these theories evolution is governed by matrix multiplication/ operator
application of some kind and that people in the know could extract
the computational complexity of this operator? Is it p-time?
A Turing Machine that just tried out all possible next states from the
current would run in p-space, but it wouldn't necessarily ``know'' when
it hit the correct next state to stop. My feeling is that there should
be enough uniformity in physics that the answer ought to be very
recursive that is at most a fixed stack of exponentials, but I don't
know enough to say anything.
Chris
Ed Fredkin
Oct27-04, 10:59 AM
<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>Chris Pollett <cpollett@yahoo.com> wrote in message news:<zt2fd.9800\\$6q2.1135@newssvr14.news.prodigy .com>...\n> Hi,\n>\n> I come from a computer science/logic background and I had some questions\n> that are directed towards those who have put forward discrete\n> models for the universe. Basically, I have some naive intuitions about\n> how such a theory would have to work and was thinking this might yield\n> some consequences about the complexity of the universe, so I was\n> wondering how off-base my assumptions were?\n>\nWe already know that physics allows for computation universality\n(Turing machines and computers) so it\'s true that a discrete model of\nphysics would also need to be universal. The first question with a\ndiscrete model (meaning space, time and state all discrete) is how to\nreconcile those characteristics with the continuous symmetries of\nphysics. One way is to design the discrete model so that it conserves\nthe quantities of physics that are related to the symmetries by\nNoether\'s theorem. It has been shown that very simple cellular\nautomata can actually conserve the digital representations of\nmomentum, spin, and other quantities exactly!\n\nThere are lots of properties of Cellular Automata that are suggestive\nof physical phenomena, such as the "particles" in Conway\'s Game of\nLife. Other CAs support wave propagation. Dan Miller has discovered,\nin a CA called "Salt" simple 3D gliders that can be configured to move\narbitrarily slowly. Nevertheless, all of the current ideas of modeling\nphysics with CA\'s are still quite primitive, with lots of non-physical\ncharacteristics. On a positive note, such models have steadily become\nless primitive over the past 40 years.\n\nFinally, a computation universal CA that conserves a large number of\nquantities can have certain properties in common with QM. From inside\nsuch as system it is never possible to get complete state information.\nThat fact combined with Universality can result in sufficient\ncomplexity as to be indistinguishable from non-determinism. All the\nwhile, the exactly conserved quantities that cause the apparent\nsymmetries can also be the root cause of the many kinds of\nmathematical laws that we find throughout physics.\n\nEd F\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form"> View this Usenet post in original ASCII form </a></div><P></jabberwocky>Chris Pollett <cpollett@yahoo.com> wrote in message news:<zt2fd.9800$6q2.1135@newssvr14.news.prodigy.com>...
> Hi,
>
> I come from a computer science/logic background and I had some questions
> that are directed towards those who have put forward discrete
> models for the universe. Basically, I have some naive intuitions about
> how such a theory would have to work and was thinking this might yield
> some consequences about the complexity of the universe, so I was
> wondering how off-base my assumptions were?
>
We already know that physics allows for computation universality
(Turing machines and computers) so it's true that a discrete model of
physics would also need to be universal. The first question with a
discrete model (meaning space, time and state all discrete) is how to
reconcile those characteristics with the continuous symmetries of
physics. One way is to design the discrete model so that it conserves
the quantities of physics that are related to the symmetries by
Noether's theorem. It has been shown that very simple cellular
automata can actually conserve the digital representations of
momentum, spin, and other quantities exactly!
There are lots of properties of Cellular Automata that are suggestive
of physical phenomena, such as the "particles" in Conway's Game of
Life. Other CAs support wave propagation. Dan Miller has discovered,
in a CA called "Salt" simple 3D gliders that can be configured to move
arbitrarily slowly. Nevertheless, all of the current ideas of modeling
physics with CA's are still quite primitive, with lots of non-physical
characteristics. On a positive note, such models have steadily become
less primitive over the past 40 years.
Finally, a computation universal CA that conserves a large number of
quantities can have certain properties in common with QM. From inside
such as system it is never possible to get complete state information.
That fact combined with Universality can result in sufficient
complexity as to be indistinguishable from non-determinism. All the
while, the exactly conserved quantities that cause the apparent
symmetries can also be the root cause of the many kinds of
mathematical laws that we find throughout physics.
Ed F
Chris Pollett
Nov3-04, 10:05 AM
<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>Hi,\n\nAlthough this post raises some interesting issues I don\'t think it\nactually speaks to any of my initial questions. In particular:\n\nEd Fredkin wrote:\n\n>\n> We already know that physics allows for computation universality\n> (Turing machines and computers) so it\'s true that a discrete model of\n> physics would also need to be universal. The first question with a\n> discrete model (meaning space, time and state all discrete) is how to\n> reconcile those characteristics with the continuous symmetries of\n> physics. One way is to design the discrete model so that it conserves\n> the quantities of physics that are related to the symmetries by\n> Noether\'s theorem. It has been shown that very simple cellular\n> automata can actually conserve the digital representations of\n> momentum, spin, and other quantities exactly!\n>\n\nThe computational universality of physics just says I can come up with\nsome physical process that simulates a Turing Machine. In my initial\npost, what I was interested in is an upper bound on the complexity of\nthe ``next step\'\' operator for the universe. That is, given the complete\nstate for things that have occurred of arc-length less than a certain\ndistance from the big bang, how hard is it to calculate a complete\nstate for things that have occurred within the next discrete allowable\narclength? My conjecture is that this next step might be polynomial time\ncomputable in this arclength since the universe is finite dimensional\nand the function is hopefully uniform. (Noether\'s Theorem mentioned\nabove might be useful in showing some kind of uniformity.) I gave some\nreasoning as to why the number of possible next steps under some\nassumptions might be exponentially bounded. For usual Turing machines\ndefinitions the next step from a given step can be verified in linear\ntime so computational universality doesn\'t seem to be relevant to my\nquestion.\n\nThe material in the rest of post was interesting -- I didn\'t know about\nthe current of research about the state of computational universal CAs\n-- but didn\'t really answer my question.\n\nAnother point I\'d like to briefly make is that we will only probably\never observe arclengths of finite distance from the big bang, so if the\ncomputation can be bounded as I suggest, then the allowable things we\ncan observed are probably simply computable functions of what was around\nat the big bang.\n\nChris\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form"> View this Usenet post in original ASCII form </a></div><P></jabberwocky>Hi,
Although this post raises some interesting issues I don't think it
actually speaks to any of my initial questions. In particular:
Ed Fredkin wrote:
>
> We already know that physics allows for computation universality
> (Turing machines and computers) so it's true that a discrete model of
> physics would also need to be universal. The first question with a
> discrete model (meaning space, time and state all discrete) is how to
> reconcile those characteristics with the continuous symmetries of
> physics. One way is to design the discrete model so that it conserves
> the quantities of physics that are related to the symmetries by
> Noether's theorem. It has been shown that very simple cellular
> automata can actually conserve the digital representations of
> momentum, spin, and other quantities exactly!
>
The computational universality of physics just says I can come up with
some physical process that simulates a Turing Machine. In my initial
post, what I was interested in is an upper bound on the complexity of
the ``next step'' operator for the universe. That is, given the complete
state for things that have occurred of arc-length less than a certain
distance from the big bang, how hard is it to calculate a complete
state for things that have occurred within the next discrete allowable
arclength? My conjecture is that this next step might be polynomial time
computable in this arclength since the universe is finite dimensional
and the function is hopefully uniform. (Noether's Theorem mentioned
above might be useful in showing some kind of uniformity.) I gave some
reasoning as to why the number of possible next steps under some
assumptions might be exponentially bounded. For usual Turing machines
definitions the next step from a given step can be verified in linear
time so computational universality doesn't seem to be relevant to my
question.
The material in the rest of post was interesting -- I didn't know about
the current of research about the state of computational universal CAs
-- but didn't really answer my question.
Another point I'd like to briefly make is that we will only probably
ever observe arclengths of finite distance from the big bang, so if the
computation can be bounded as I suggest, then the allowable things we
can observed are probably simply computable functions of what was around
at the big bang.
Chris
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.