# Nebel's approach to recursive definitions

David A. McAllester <dam@ai.mit.edu>
Date: Thu, 26 Jul 90 16:57 EDT
From: David A. McAllester <dam@ai.mit.edu>
Subject: Nebel's approach to recursive definitions
To: norvig@teak.berkeley.edu, interlingua@vaxa.isi.edu
Message-id: <19900726205755.8.DAM@CROCE.AI.MIT.EDU>

I just looked at the chapter of Nebel's thesis on recursive definitions.
He discusses least fixed points and greatest fixed points and rejects
both in favor of an ``any fixed point'' semantics (at least that is my
reading of his ``descriptive semantics'').
Least fixed points are the only semantics considered by Nebel that allow
that conclusion that every descendent of a human is human. The mu
calculus that I proposed in my first message is based on least fixed
points. I am not impressed by Nebel's criticism of least fixed point
semantics. However, I do know of some significant arguments against
using the mu calculus as the only semantic foundation of recursive
definitions.
In developing a foundation for recursive definitions it is important, I
think, to put forward some clear alternatives. The mu calculus provides
one possible foundation for recursive definitions which (at least)
justifies the deduction that every descendent of a human is human. The
mu calculus is NOT scarry or complicated. Using the mu calculus as the
foundation, there is no need to discuss the complicated domains needed
for program language semantics (Scott-Stratchy domains and the
associated lattice-theoretic hair can be safely ignored). I think I
could make everyone fully understand the mu calculus with a fifteen
minute presentation at the meeting. In general, I would like to avoid
domain-theoretic hair (I am convinced that domain-theoretic hair is not
needed).
David