From avrim@archimedes.theory.cs.cmu.edu Wed Jul 5 15:56:19 2000
Date: Wed, 5 Jul 2000 15:55:49 -0400
From: Avrim Blum
Subject: comments on your FOCS submission -The computational power of iterating
Below are comments-for-authors (if any) on your FOCS-2000 submission.
These are intended as feedback that we hope will be useful to authors
whatever decision was made. They are not necessarily intended to
explain the reasoning behind the committee's decisions, and in
general will not be representative of that reasoning.
Best Regards,
Avrim Blum
PC Chair, FOCS 2000
=============================================================================
wds: I include the referee report below, plus comments by me prefaced "wds:".
=============================================================================
REFEREE REPORT:
The main result of this paper is an extension of an old result,
stating that the iteration of an analytic function has universal Turing
computational power. The extension allows the function to be entire
as well as perturbed by noise.
Besides this result, an important part of the paper is devoted to
critique the BSS notion of decidability over the reals for which
the author suggests an alternate definition.
The following are some additional remarks.
\begin{itemize}
\item
The fact that any open subset of $\R^n$ is BSS semidecidable is well known
(see for instance F. Cucker, J.L. Monta\~na and L.M. Pardo,
{\em Int. J. of Algebra and Computation}, 2, pp. 395--408, 1992).
Thus, there is no novelty in showing that one can decide whether a point
belongs to the Mandelbrot set if the point belongs to its interior.
--wds: actually, the following subset of R^2:
{x,y | my analytic fn iteration "halts" starting from here}
(where you can use various definitions of the "halt" state,
it does not matter terribly much which)
and its complement, are both well behaved sets with nice smooth boundaries.
(Anyway even if not, we can restrict to such nice sets artificially.)
If we restrict to their interiors, we get 2 disjoint open
sets. Evidently, one of these 2 open subsets of R^2 is NOT BSS
semidecidable. This counterexample contradicts the "well known" claim
by the referee.
It is unfortunate that the referee was deluded on this point.--wds
\item
The fact that $\{(x,y)\in\R^2\mid y\leq e^x\}$ is not BSS decidable is
folklore. If one wants the exponential (and a few more elementary functions)
to be decidable, it is enough to add them to the BSS model either directly
or by using oracles (as in E. Novak, {\em J. of Complexity} 11, pp. 57--73,
1995). In practice, the exponential function is approximated by
polynomials. Thus, to add it to the basic BSS model would be in
agreement with both the BSS computability
and a long tradition in approximation theory.
--wds: It is hard to argue with an unsupported claim something is
"folklore"... so I will not... if it is folklore, all I can say is,
it is a bit strange that BCSS, in their book allegedly summarizing the
whole field, did not manage to mention this, since it represents a
nicer example of "BSS-undecidability" than the examples they did
give. And ditto for all the papers in the area I've managed to find...
(and its proof is quite nontrivial, depending on some heavy results
from number theory..., although once those results are known, the
proof becomes pretty easy.) Don't you think it would be a
little bit better if some publication actually MENTIONED this piece of
"folklore"? As opposed to the approach of preventing anyone from ever
mentioning it in print, on the grounds that it is folklore??
The referee in any case apparently misses the main point, which is,
that whether this is folklore or not, it makes it evident the BCSS
decidability definition is a silly one which ought to be replaced by a
better one. Namely, if a set this easy to decide is "undecidable" then
the definition of "undecidable" was silly - we ought to have a better
definition of "undecidable" in which easy sets are decidable and hard
sets are not!
Finally, the Novak paper is a did-nothing paper with no results in it,
and the latest idea of the referee would seem to yield the conclusion
that ALL analytic functions should be added to the BSS model, which
would result in one heck of a different model, and is hardly a small step!
Indeed, merely adding exp to the model alone would change its complexity
properties VASTLY. Thus this offhand remark is extremely deceptive.--wds
\item
The author claims that the book by BCSS does not provide a proof
of the undecidability of the Mandelbrot set. Such a proof, although
sketchy, is in page 68 of [BCSS]. And it uses the fact that the
boundary of the Mandelbrot set has Haussdorf dimension 2 in such a way
that any other subset of $\R^2$ whose boundary has Haussdorf dimension
2 would be also BSS undecidable. Thus, the sentence in the abstract
``Neither [\dots] nor the fact that its boundary has Haussdorf
dimension 2, need have anything to do with the undecidability''
is meaningless.
--wds: I'll now quote the "proof, although sketchy" on page 68 of BCSS
in full: "A direct proof of lemma 3 is folklore following discussions
with M.Herman, A.Douady, J.Hubbard, and D.Sullivan." I am afraid I do
not understand why the referee thinks this is a proof. Even a sketchy
one. (And "Lemma 3" is the key fact that "any other subset of $\R^2$ whose
boundary has Haussdorf dimension 2 would be also BSS undecidable" the
referee needs.) BCSS also confuse M with the boundary of M, which makes
things less valid still. BCSS page 68 also cite L.Blum and S.Smale:
The G\"odel incompleteness theorem and decidability over a ring,
321-339 in From Topology to Computation Proceedings of Smalefest
(ed.M.W.Hirsch, J.E.Marsden, M.Shub) Springer 1990 as the source of
their theorem 1 (that Mandelbrot is undecidable). But the proof given
in this cited paper (p.337-338) is not a proof either. I quote the last
2 sentences of that "proof":
"Therefore, $\partial M intersect S_i$ is contained in $\partial M
intersect S_i$ and has [Haussdorf] dimension $\le 1$. So now we have
$\partial M = \Union_{i=1}^\infty (\partial M intersect S_i)$ has
[Haussdorf] dimension $\le 1$."
Observe in these two sentences that first, it seems a little bit
vacuous to say X is contained in X. Presumably the authors wanted
to say something non-vacuous instead, perhaps
"$\partial M intersect S_i$ is contained in $\partial (M intersect S_i)$"
or perhaps
"$\partial M intersect S_i$ is contained in $\partial S_i$."
Second, their following sentence depends implicitly on the assumption
(although they did not bother to say so) that if the boundary
$\partial M$ of a subset $M$ of $R^2$ is the union of a countable
number of sets, each of which is the Haussdorf dimension 1 boundary of
a semialgebraic set, then the Haussdorf dimension of $\partial M$ must
be $\le 1$.
That assumption in turn (although they again did not bother to say so)
would seem to depend upon the assumption that, if you have
a countable set of positive-valued functions f_1(r), f_2(r), f_3(r)...,
each of which has the property that |log f_i(r) / log r|-->1 as r-->0+,
then |( log sum_i f_i(r) ) / log r|-->1 as r-->0+.
However, counterexamples to this assumption may be constructed!
[Hint: first consider constructing a counterexample to
the simpler related conjecture that if you have
a countable set of positive-valued functions f_1(r), f_2(r), f_3(r)...,
each of which has the property that f_i(r)-->const_i>0 as r-->0+,
then sum_i f_i(r) --> const as r-->0+. A counterexample involves
f_i(r) being a gaussian(r) where the Gaussian's get sharper and sharper
and higher and higher as i-->infinity.]
Thus, not only is there not a proof in BCSS, in fact there has been
no valid proof in the literature, ever, before my proof, that
M is BSS-undecidable.
(I would be happy to see the Blum-Smale proof rescuscitated somehow, which
plausibly is possible. All I am saying now, is it obviously is not a proof
as it stands.)
It is unfortunate that the referee was deluded on this point, and prefers
non-proofs to actual proofs to the extent of preventing publication
of the latter.
Next, the referee's claim is misleading and verging on false:
First, open subsets of R^2 whose boundaries have Haussdorf dimension
2 DO exist which ARE BSS-decidable... except for points exactly on
that boundary. A sketch of one construction is as follows (quite
sketchy, although far less so than BCSS p.68): consider a
"fractal"-like set defined by an augmentational edge replacement rule
like the Koch snowflake, except each edge is replaced by a sawtooth
whose teeth keep getting narrower and narrower in aspect ratio
approaching infinite aspect ratio on the nth stage as n-->infinity, so
that the fractal dimension approaches 2. The Koch snowflake's
complement is also constructible by a pure-augmentational replacement
rule and one can work similarly in our case. Then by simultaneously
constructing the snowflake and its complement algorithmically to
greater and greater accuracy, we ultimately must terminate with a
proof x,y is either inside or outside our set (unless x,y is exactly
on the boundary). If x,y is exactly on the boundary, then in the case
where we demand x,y be algebraic, or in the case where we demand
immunity to infinitesimal "noise" we can make the decision
algorithmically again. So, as usual, the only difficulty arises when
x,y is exactly on the boundary and non-algebraic, thus as usual
highlighting the specific wrongheaded nature of the BSS undecidability
definition.
Second, open subsets of R^2 whose boundaries have Haussdorf
dimension ANYTHING (besides 1) are BCSS undecidable, to the extent
this is true for Haussdorf dimension 2... i.e. a generic curve with
Haussdorf dimension H, for any 1