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?

$\endgroup$
  • 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 '17 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 '17 at 22:12
  • 1
    $\begingroup$ I believe John Reif answered this question (affirmatively) in the 1990s. $\endgroup$ – Jeffε Jul 22 '17 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 '17 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 '17 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.