Re: Language vs. Library why it matters

*To*: mathgroup at smc.vnet.net*Subject*: [mg61563] Re: Language vs. Library why it matters*From*: "Richard J. Fateman" <fateman at eecs.berkeley.edu>*Date*: Sat, 22 Oct 2005 00:36:32 -0400 (EDT)*Organization*: UC Berkeley*References*: <dja2ht$fll$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Bill Rowe wrote: > > > My intent was merely to make the point Godel's results must apply >to Mathematica since they clearly apply to mathematics and Mathematica >by design is intended to encompass mathematics. Not so. Mathematica does not prove theorems, generally. Some mathsource programs may construct some proofs in some limited context, but those don't contradict Godel's result. Mathematica running on your computer is not, actually, as powerful as the simplest Turing machine. The "Halting Problem" for Mathematica on your computer is solvable. You have a finite machine with a finite number of states. It is possible in principle to tell if a program is in a loop or if it will halt. The testing procedure may take a very long time to run, but the testing procedure is also finite. Or perhaps you are trying to state something else about decidability. One can state classes of problems for which no algorithm can exist in Mathematica. (or C or Fortran or executable by the finite collection of atoms that constitute a single human brain, or for that matter the collective brains of all humans living and dead....) For example, Hilbert's 10th problem http://mathworld.wolfram.com/DiophantineEquation.html But this does not prevent one from finding solutions to a subset of that class of problems. Perhaps the subset of Diophantine Equations that can be expressed in less than 2^40 ASCII character in Mathematica syntax can be solved. That would not contradict the theorem, but it would take the bite out of it. If you want to explore decidability, Frege, Whitehead/Russell, Godel, Turing, ... that's fine, but don't confuse it with defects in computer algebra system design. As for whether Mathematica or anything else can "arithmetize" all of mathematics, you might look at the QED project, archived at http://www-unix.mcs.anl.gov/qed/ or at some of the more recent work.. google for MKM. RJF