9
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Max New
    Jul 20, 2017 at 12:14
  • $\begingroup$ @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. $\endgroup$
    – Miles Rout
    Jul 20, 2017 at 22:12
  • 1
    $\begingroup$ I believe John Reif answered this question (affirmatively) in the 1990s. $\endgroup$
    – Jeffε
    Jul 22, 2017 at 6:59
  • 2
    $\begingroup$ 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. but I did not understand if it implies turing completness or not. $\endgroup$
    – Xavier Combelle
    Jul 27, 2017 at 10:01
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – mhum
    Jul 27, 2017 at 21:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.