       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:=
FindInstance[
x^3+y^3==z^3 && x>0 && y>0 && z>0,
{x,y,z}, Integers] // Timing

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

Out=
{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:=
FindInstance[x^3+y^3==z^3&&x>0&&y>0&&z>0,{x,y,z},Integers]//Timing

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

Out= {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

```

• Prev by Date: Re: Help with NMinimize
• Next by Date: Re: determine viewpoint value during V6 3d rotation
• Previous by thread: Creating a popup menubox in a specified notebook
• Next by thread: Re: A riddle: Functions that return unevaluated when they