However, what should be the type of
the example (1) below?
(1) -> res := guess([product(1+factorial k, k=0..n-1) for n in 0..6],
[guessPRec], [guessProduct])
n - 1
++-++
(1) [ | | [f(p ): f(p + 1) + (- p - 1)f(p ) + p = 0,f(0)= 2]]
| | 7 7 7 7 7
p = 0
7
You believe that I understand that output?
given what I tried to clarify so far, I was hoping so. It is
\prod_{p=0}^{n-1} f(p)
where f(p) is given by the recurrence
f(n+1) = (n + 1) f(n) - n; f(0) = 2
(as it turns out, f(n) = n! + 1)
1) \prod_{p=0}^{n-1} f(p) and the output of (1) look a bit different
with respect to the brackets. That's my first problem.
2) Looks like for specifying f(p) a difference operator with
coefficients in Z[p] would be sufficient. Now, to represent the product
sign, it's probably enough here, that you store the upper bound, (and
maybe the variable p and the lower bound 0). So you get something like a
triple (lower-bound, upper-bound, difference operator).
But you wanted to trick me, guess is actually what I would call the user
interface. And here (without deeper inside into the guessing business) I
would agree in returning Expression(..) for the moment.
You probably tell me in the next mail... "Well, the returned object
could be a product of a sum of products." I'd say, if that is the only
pattern, then even that would be managable without going to Expression(R).
I was speaking about the more particular functions, though. Like guessADE.
I've currently no idea what kind of expressions there your functions
might return, but although that what Kauers defined (admissible
sequences/functions) is in some sense a bit better than just allowing
every expression as an output. Can't you restrict your solution space,
i.e. cannot you describe the solution space/domain in mathematical terms?
And by the way, if you use Expression(Integer) only because you can
have nice output,
no, that's not the reason at all. I know well how to use OutputForm.
Yes, yes, I believe that. Sorry, if I sounded rude.
Since in mantepse.spad I don't actually see Expression(...) as an
input, can you (apart from you design decision above) say why you
actually need the Expression domain at all? My suspicion is that like
with the (multivariate) polynomial that could be used as the return
type for guessADE, you might have more specific types for all the
other functions, too.
I cannot find a reasonable type for guess (for guessing products and
sums), guessBinRat and guessExpRat , and I'm not sure what types I
should introduce at all.
If you want the guess return type be the union of all the (more
specific) return types of guessSum/guessProduct/guessBinrat/... then
there is a Union type in SPAD that sits right in front of you.
(Although, I also wouldn't find this the optimal solution.)
> Eg., should guessPade, guessAlg, guessHolo,
guessADE, guessFE return different types or not? (certainly we have
guessPade< guessAlg< guessHolo< guessADE
where x< y means that every x is also an y.) That's certainly a nice
hierarchy, and I'd really like to have such types.
Every guessAlg is also a guessADE??? There is only one function guessAlg
and only one function guessADE. What do you mean?
You probably have something nice in mind, but you haven't yet expressed
it in a clear way. Sorry, but I cannot follow. Can you make that more
precise?
> How about
guessHolo(q) and guessADE(q)
and
guessFE
(the latter class doesn't seem to enjoy any useful closure properties).
What should I tell you? Please give a clear specification of input and
output so that I have something to think about. Currently I just see
function names.
Concerning types for sequences: how should I deal with the problem, that
an equation returned by guessRec does not necessarily determine a formal
power series, eg:
(39) -> guessRec [1,1,1,0,0,1,0,0,1,0]
2
(39) [[f(n): - f(n) + f(n)= 0]]
Type: List(Expression(Integer))
Again, I cannot interpret the output. I am not Martin Rubey. For me the
input/output behaviour of guessRec is not clearly specified. So what
should I say?
Let's take your pseudo-specification on page 3:
Given is f: N -> K (i.e. a sequence, where N is the natural numbers and
K is a field). (BTW, your article doesn't say that n ranges only over
natural numbers. Is the letter n in some way special that I am supposed
to assume n ranges over N?---That would be relevant for your equation
(6), because that has to hold for every n (of what range?). Don't say
for an indeterminate n, because f is a function N->K, i.e. not specified
for indeterminates.)
Then you say,
guessRec find recurrences of the form
(6) p(f(n), f(n + 1), . . . , f(n + k)) = 0,
where p is a polynomial with coefficients in K[n].
Then you give an example. But examples are not specifications, i.e.
irrelevant.
Where did you specify the input to guessRec? And what has the input to
do with the given f?
Let me try.
Input: A list [f(0),...,f(m)] for some integer m>0.
Output: k an integer, 0 <= k <= m
p a polynomial in K[n][x_0,...,x_k]
Property: forall n \in \{0,..,m-k\}:
p(f(n), f(n + 1), . . . , f(n + k)) = 0
OK. What do we see? It is completely irrelevant that there is a sequence
f: N -> K. The f is actually only needed to have some letter that you
can index.
The above specification is certainly not what you want, because it
should specify that p is a nonzero polynomial if there exists a nonzero
polynomial with the above property. (Otherwise, as a programmer, I would
implement guesRec to always return the zero polynomial---which would be
actually a perfect implementation of guessRec according to your
pseudo-specification.)
Don't mix the specification with the implementation.
I guess, one might want that in the polynomial p every of the variables
x_0,...,x_k actually occurs. Right?
As a matter of fact, the guessing package is really intended to be used
by the end user only, and will probably always be a prototype.
Nobody tries to write programs. How can you do *mathematics* with not
fully specified programs?
OK, your code is a guesser, so proofs are missing anyway. ;-)
But if you look at my specification (maybe it does not completely cover
your intention), then that is in no way a guesser. The output is
algorithmically checkable.
Later as a second step (without running any algorithm), one could take
the output and claim it does not only hold for n from 0 to m-k but for
all natural number n. Then, of course, I would have to define what
f(m+1), f(m+2), etc. actually is.
But this second step is the guessing. Running the program is not.
Ralf
--
You received this message because you are subscribed to the Google Groups "FriCAS -
computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
