Transcript Making Computers Do Math - University of California, Berkeley

Making Computers Do Math
Prof. Richard Fateman
Fall, 2001
University of California,
Berkeley
Oct 30, 2001 Richard Fateman
1
What could we possibly
mean?
• Solve applied mathematics problems
– Convert math statements to effective
algorithms (programs)
– Follow specific commands to perform algebraic
transformations
• Prove theorems
– or Search for counter-examples
• Prove programs correct (combine previous ideas!)
• Read (and write!) texts and handbooks to produce
indexed re-usable math knowledge
Oct 30, 2001 Richard Fateman
2
Brute force algebra...
@
H LD
Expand
x+ y + z ^8
x8 + 8 x7 y + 28 x6 y2 + 56 x5 y3 + 70 x4 y4 + 56 x3 y5 + 28 x2 y6 + 8 x y7 +
y8 + 8 x7 z + 56 x6 y z + 168 x5 y2 z + 280 x4 y3 z + 280 x3 y4 z +
168 x2 y5 z + 56 x y6 z + 8 y7 z + 28 x6 z2 + 168 x5 y z2 +
420 x4 y2 z2 + 560 x3 y3 z2 + 420 x2 y4 z2 + 168 x y5 z2 +
28 y6 z2 + 56 x5 z3 + 280 x4 y z3 + 560 x3 y2 z3 + 560 x2 y3 z3 +
280 x y4 z3 + 56 y5 z3 + 70 x4 z4 + 280 x3 y z4 + 420 x2 y2 z4 +
280 x y3 z4 + 70 y4 z4 + 56 x3 z5 + 168 x2 y z5 + 168 x y2 z5 +
56 y3 z5 + 28 x2 z6 + 56 x y z6 + 28 y2 z6 + 8 x z7 + 8 y z7 + z8
Oct 30, 2001 Richard Fateman
3
Is Math an AI problem?
Oct 30, 2001 Richard Fateman
4
Is Math an AI problem?
•
Can we build a math expert?
– Must we build an artificial intelligence?
– Can we teach math with or without other
interactions?
– Obvious success in limited domains.
– All of math? Not so easy!
Oct 30, 2001 Richard Fateman
5
Complex domains,
representation problems?
àB@
@
D
DàF
¥
0
Exp a x â x
If Re a
<
0,
-
1
,
a
Oct 30, 2001 Richard Fateman
¥
0
ax
E
â
x
6
Is doing Math a GUI
Problem?
• Plot3D[Sin[x*y],{x,0,4},{y,0,4}]
1
0.5
4
0
-0.5
-1
0
3
2
1
2
3
0
Oct 30, 2001 Richard Fateman
4
1
7
Can the world-wide web do
what a single computer
cannot do?
Oct 30, 2001 Richard Fateman
8
Yes, in some ways
•
Access the library to get printed or
on-line data about a topic
• Answer specific questions using education-level
appropriate approaches on topics from elementary
school arithmetic through calculus to advanced
math (Distributed Expert)
• Search in on-line databases for relevant articles,
programs, formulas to help solve problems.
• Fix, update central repository of know-how
Oct 30, 2001 Richard Fateman
9
What else ?
•
Communicate among active servers: can we have
networked solvers cooperating or competing to
solve problems?
• Encode math formulas so that multiple programs
(CAS, TeX, Editor, numeric compiler) can
communicate with a common channel
• MathML/XML ?
Oct 30, 2001 Richard Fateman
10
Tools
• Computer algebra systems, general or special
purpose
– Mathematica, Maple, Macsyma, GAP, PARI,
• Interactive computer systems for scientific
calculation
– Matlab, Octave, MathCad
• Library research systems
– NEC ResearchIndex
– California Digital Library
Oct 30, 2001 Richard Fateman
11
Very specific topics
Oct 30, 2001 Richard Fateman
12
TILU, Table of Integrals
LookUp
•
Building the world's most expert (human or nonhuman) symbolic indefinite and definite
integration program, on-line.
–
–
–
–
Algorithms
Tables
Generation of new solutions
Archiving newly found information
Oct 30, 2001 Richard Fateman
13
Code generation
•
The generation of highly specific and
maximally efficient programs for certain
numerical computations, e.g. approximate
solution of differential equations tuned to
specific equations or specific computers or
specific memory configurations. Numerical
routines based on difficult-to-program
symbolic approximations such as Taylor
series.
Oct 30, 2001 Richard Fateman
14
“Expert” shells / Search
•
The building of expert shells for stating and
solving problems.
•
Assisting NEC's ResearchIndex project to
decode postscript specifications of journal article
pages tofind math, and encode the math in (say)
TeX. Allowing it to be indexed.
Oct 30, 2001 Richard Fateman
15
Graphical User Interfaces
•
Building universal front ends that
understand math typing and even
handwriting (Biscotti, Texmacs,
Livemath, Graphing Calculator) ...and
that talk to everyone else.
– Naive vs. skilled humans:
– Who knows that xsinx is the same as x sin(x)?
Oct 30, 2001 Richard Fateman
16
Macsyma / open source
• Re-building the Macsyma computer
algebra system as open-source:
• an opportunity to re-engineer in
current technology;
• convert to a tool-based orientation;
• combine with other programs Octave,
Texmacs, Pari,
• advanced algorithms
Oct 30, 2001 Richard Fateman
17
Current Funding
• 1+ funded new research
assistantships (NSF) for projects
related to computer algebra/
scientific environments
• (possible) additional funding for
digital library related activity.
• [email protected]
Oct 30, 2001 Richard Fateman
18