[FOM] On Physical Church-Turing Thesis

José Félix Costa fgc at math.ist.utl.pt
Thu Feb 12 06:18:19 EST 2004

About Dmytro's

Notice that in classical mechanics, the n-body problem in gravitation is
decidable up to the moment of a collision or ejection to infinity, when the
theory breaks down because of faulty

We have been talking about the mathematical model. (Limitations are not
built in the classical mathematical description of Newtonian mechanics.)

If you consider n-body collisions on the horizontal plane of the gravitic
field (collision experiences without an effective field) were collisions are
elastic (kinetic energy preserved in collisions) than you have all
undecidabilities of classical computation.

Proofs were presented in

Conservative logic
by Edward Fredkin and Tommaso Toffoli
Int. J. Theor. Phys. 21 (1982), 219-253.

But if we look at general, then we have quite «new» computational
undecidable problems like «the stability problem» inter alia such as in

Overview of complexity and decidability results forthree classes of
elementary nonlinear systems
by Blondel and J. Tsitsiklis
Lecture Notes in Control and Information Science, Learning, Control and
Hybrid Systems, Y. Yamamoto and S. Hara (Eds), pp. 46-58, Springer Verlag,
Heidelberg, 1998.


J. Felix

J. Felix Costa
Departamento de Matematica
Instituto Superior Tecnico
Av. Rovisco Pais, 1049-001 Lisboa, PORTUGAL
tel:      351 - 21 - 841 71 45
fax:     351 - 21 - 841 75 98
e-mail:   fgc at math.ist.utl.pt
www:    http://fgc.math.ist.utl.pt/jfc.htm

More information about the FOM mailing list