<p>Seemingly simple things have turned out to be capable of computation - Conway's Game of Life, Wolfram's Rule 110, etc.</p>

<p>Has anyone devised a Turing complete system using suns, planets, moons, sub-moons, etc? Just inert chunks of matter in space behaving according to Newtonian physics that perform computation?</p>

CC BY-SA 3.0
2017-07-20T12:14:22.840Z
Turing completeness requires unbounded memory, so such a system would require some kind of infinitary physical system: infintely large or arbitrarily small matter or violating conservation of matter.
Max New
CC BY-SA 3.0
2017-07-20T22:12:08.957Z
@MaxNew You 'just' need to be able to detect arbitrarily small differences in orbits. You could 'store' the tape as just encoding the contents of the tape as an integer, then 'storing' that integer in some physical property of the system (e.g. the orbit of a particular planet is 100,000 km + 1/x km). how you get that number out is a separate question of course, but I dunno, maybe you can make the magnitude of the difference in the orbit caused by a position on the tape related to how far the head is from that location on the tape, or something.
mrr
CC BY-SA 3.0
2017-07-21T04:34:54.777Z
@MaxNew - as Miles Rout said, I think in this "world", finite matter in infinite space gives you infinite memory.
obelia
CC BY-SA 3.0
2017-07-22T06:59:34.993Z
I believe John Reif answered this question (affirmatively) in the 1990s.
Jeffε
CC BY-SA 3.0
2017-07-27T10:01:39.803Z
I found this reference  [Beggs, E. J., & Tucker, J. V. (2007). Can Newtonian systems, bounded in space, time, mass and energy compute all functions?. Theoretical Computer Science, 371(1-2), 4-19.](http://dl.acm.org/citation.cfm?id=1225563) but I did not understand if it implies turing completness or not.
Xavier Combelle
CC BY-SA 3.0
2017-07-27T21:41:29.813Z
@XavierCombelle In fact, that Beggs & Tucker paper presents a model of computation based on Newtonian kinematics that is even _stronger_ than Turing completeness. They claim their model can recognize _any_ subset of $\mathbb{N}$.
mhum
<turing-machines>
Is there a Turing complete planetary system?
obelia
# Is there a Turing complete planetary system?

(Asked by: username_0 on 2017-07-19)

Seemingly simple things have turned out to be capable of computation - Conway's Game of Life, Wolfram's Rule 110, etc.

Has anyone devised a Turing complete system using suns, planets, moons, sub-moons, etc? Just inert chunks of matter in space behaving according to Newtonian physics that perform computation?

**Tags:** turing-machines

> **Comments:**
> **username_1**: Turing completeness requires unbounded memory, so such a system would require some kind of infinitary physical system: infintely large or arbitrarily small matter or violating conservation of matter.  
> **username_2**: @MaxNew You 'just' need to be able to detect arbitrarily small differences in orbits. You could 'store' the tape as just encoding the contents of the tape as an integer, then 'storing' that integer in some physical property of the system (e.g. the orbit of a particular planet is 100,000 km + 1/x km). how you get that number out is a separate question of course, but I dunno, maybe you can make the magnitude of the difference in the orbit caused by a position on the tape related to how far the head is from that location on the tape, or something.  
> **username_0**: @MaxNew - as Miles Rout said, I think in this "world", finite matter in infinite space gives you infinite memory.  
> **username_3**: I believe John Reif answered this question (affirmatively) in the 1990s.  
> **username_4**: I found this reference  [Beggs, E. J., & Tucker, J. V. (2007). Can Newtonian systems, bounded in space, time, mass and energy compute all functions?. Theoretical Computer Science, 371(1-2), 4-19.](http://dl.acm.org/citation.cfm?id=1225563) but I did not understand if it implies turing completness or not.  
> **username_5**: @XavierCombelle In fact, that Beggs & Tucker paper presents a model of computation based on Newtonian kinematics that is even _stronger_ than Turing completeness. They claim their model can recognize _any_ subset of $\mathbb{N}$.  

---

## 0 answers

