Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That's … unsatisfying. I mean that it's unsatisfying in a theoretical sense (because it gives me no theoretical feeling for the Turing-machine-to-differential-equation transformation), but, if I really wanted to be picky, I could point out that (a) nothing in the definition of a Turing machine guarantees its physical realisability (what if its number of states is bigger than the power set of the number of elementary particles in the universe, or, similarly, if it writes on an unbounded amount of tape?), and (b) Newton's equations of motion are only approximations to, not exact descriptions of, the physical universe.

Is there any more-or-less explicit recipe that says "given a description of a Turing machine (as a 7-tuple, say https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...), here is a (possibly unmanageably huge) differential equation such that …"—well, I don't even really know what. Your answer suggests that I might ask that, say, the solution $y$ to the differential equation where $y(1)$ somehow encodes a given initial state of the tape is such that $y(0)$ somehow encodes the final state of the tape (with the understanding that $y$ is not defined at $0$ if the machine doesn't halt on the corresponding input).



Fine, fine, I just think it's an elegant way to say it :)

You want something like this http://www.sciencedirect.com/science/article/pii/S1571066108... or like this http://www.sciencedirect.com/science/article/pii/S0196885807...


> Fine, fine, I just think it's an elegant way to say it :)

You're absolutely right that it's an elegant and compelling argument for the plausibility of the claim; I was just looking for the rigour behind it (even a statement, if not a proof). Your second reference is exactly the sort of thing that I had in mind; thanks!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: