Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

A riddle: Functions that return unevaluated when they cannot solve

• To: mathgroup at smc.vnet.net
• Subject: [mg82394] A riddle: Functions that return unevaluated when they cannot solve
• From: Szabolcs Horvát <szhorvat at gmail.com>
• Date: Fri, 19 Oct 2007 04:59:08 -0400 (EDT)

There are certain functions in Mathematica which return unevaluated when 
they cannot solve the task they've been given.  Examples are 
Integrate[], Solve[], FindInstance[], etc.

How are these functions implemented?  Mathematica should evaluate 
expressions for as long as there are definitions that apply to it. 
Obviously this behaviour cannot be achieved by something like

fact[n_] := If[n >= 0, n!, fact[n]]

because this leads to infinite evaluation for negative n.

So I suppose that Integrate[] and similar functions cache their results, 
and can remember that a specific problem was unsolvable.  I imagined 
that they might be defined similarly to this:

fun[a_] := (cachedUnsolvableQ[a] = True; fun[a]) /;
   Not@cachedUnsolvableQ[a]

cachedUnsolvableQ[_] = False (* default value *)

But this is not true!  Consider the following input:

In[1]:=
FindInstance[
     x^3+y^3==z^3 && x>0 && y>0 && z>0,
     {x,y,z}, Integers] // Timing

During evaluation of In[1]:= FindInstance::nsmet: The methods available 
to FindInstance are insufficient to find the requested instances or 
prove they do not exist. >>

Out[1]=
{1.156, FindInstance[x^3+y^3==z^3&&x>0&&y>0&&z>0,{x,y,z},Integers]}

Evaluating this expression takes a relatively long time on my system (~1 
sec).  If FindInstance cached its result the way I described above, then 
subsequent evaluations should be instantaneous.  But they aren't!

In[2]:=
FindInstance[x^3+y^3==z^3&&x>0&&y>0&&z>0,{x,y,z},Integers]//Timing

During evaluation of In[2]:= FindInstance::nsmet: The methods available 
to FindInstance are insufficient to find the requested instances or 
prove they do not exist. >>

Out[2]= {1.063,FindInstance[x^3+y^3==z^3&&x>0&&y>0&&z>0,{x,y,z},Integers]}

The second calculation took as much time as the first one.  This means 
that FindInstance[] tried to solve the problem *again*, and it did not 
simply stay unevaluated.  But then why does the returned result (which 
is the same as the input) stay unevaluated?

Could someone explain how this behaviour is implemented?

Of course this does not prevent me from solving some practical problem 
in Mathematica, I'm just curious about it.

-- 
Szabolcs

• Follow-Ups:
  • Re: A riddle: Functions that return unevaluated when they
    • From: "W. Craig Carter" <ccarter@mit.edu>