# Talk:Gravity

From Esolang

I'm somewhat sure that this is "usable". --Ihope127 15:45, 27 Aug 2005 (GMT)

- I'd disagree. I haven't yet written a program that loops in any predictable fashion - I've been relying on symmetry to make the equations solvable, but with too much symmetry the language loses its power. --Safalra 16:19, 27 Aug 2005 (GMT)

- Hmm, maybe I don't really understand this... at all :-) --Ihope127 16:24, 27 Aug 2005 (GMT)

## Computability[edit]

"*It can be shown that a Turing machine cannot compute, in the general case, whether even a single collision will ever happen.*" Why and how? --BodyTag 20:45, 20 Oct 2005 (GMT)

- Good question. Apparently Penrose proved that certain questions in gravitational systems are undecidable. Unfortunately I can't remember where I read about it. --Safalra 10:28, 21 Oct 2005 (GMT)

- But the halting problem for Turing machines is also unsolvable, right? What matters is simply whether a Turing machine can compute it, not whether a Turing machine can solve the Gravity "halting problem". --Ihope127 01:01, 21 Oct 2005 (GMT)

- What's the connection? To similuate Gravity on a Turing machine you need to know when and where collisions will happen, and this can't be done. --Safalra 10:28, 21 Oct 2005 (GMT)

- Can't you just perform the gravity calculations, check for collisions, perform the calculations, check for collisions, et cetera ad infinitum? --Ihope127 19:16, 21 Oct 2005 (GMT)

- No - they're differential equations whose exact solutions are non-computable. (Incidentally, even the solutions of the differential equations for a
*three*-body gravitational system are non-computable.) --Safalra 19:43, 21 Oct 2005 (GMT)

- No - they're differential equations whose exact solutions are non-computable. (Incidentally, even the solutions of the differential equations for a

- Can't you compute it lazily then, just enough to see if there's a collision "this time"? --Ihope127 20:32, 21 Oct 2005 (GMT)

- Although Gravity is truly a unique language, if by "non-computable" we mean "undecidable" (and I think that's reasonable based on what I know about computability of differential equations, and what Safalra has said above,) then yes, it can be simulated by a Turing machine. Remember, "undecidable" is the same as "semi-decidable": we cannot say that any given event will or will not happen, but if some event
**does**happen, we**can**tell (simply by e.g. running our program and watching it.) So, I think, even in the worst case, we can have a Turing machine generate all possible proofs, one by one, and check each one to see if it is a valid proof that the given Gravity program halts and produces some result (in which case our TM halts and produces that result.) --Chris Pressey 20:24, 5 November 2007 (UTC)

- Although Gravity is truly a unique language, if by "non-computable" we mean "undecidable" (and I think that's reasonable based on what I know about computability of differential equations, and what Safalra has said above,) then yes, it can be simulated by a Turing machine. Remember, "undecidable" is the same as "semi-decidable": we cannot say that any given event will or will not happen, but if some event

This seems reminiscent of machines I have seen run using chaos theory (based on mathematics like the game of life) such as this one. Are such things listed in this wiki? Are they out of the scope of this wiki? --Stux 01:18, 21 Oct 2005 (GMT)

- So the Turing Machine can't simulate it, but can it simulate the Turing Machine?

I just have to say that this is a cool concept... --**The Prophet Wizard of the Crayon Cake** 21:16, 21 Aug 2006 (UTC)