[FOM] irrational conjectures
Vaughan Pratt
pratt at cs.stanford.edu
Fri Mar 13 15:56:46 EDT 2009
Timothy Y. Chow wrote:
> Harvey Friedman wrote:
>> WILD CONJECTURE. There exists a positive integer n < 2^1000 such that
>> the statement sin(2^[n]) > 0 can be proved using (commonly studied)
>> large cardinals using at most 2^20 symbols, but cannot be proved in ZFC
>> using at most 2^2^2^20 symbols.
>
> Obviously, one can take any unsolved problem and formulate a similar
> wild conjecture. But is there any particular reason to believe that
> large cardinals are lurking here?
Tim raises an issue that I see as having close ties with Wolfram's
Principle of Computational Equivalence, not in its general form but in
the more specific form of whether any of the 256 smallest (three-bit)
cellular automata Wolfram exhibits in Chapter 3 of ANKS exhibits
Turing-universal behavior in any "technically consistent" sense, a
concept I'll say more about shortly.
A case in point is Wolfram's rule 30, so named because 30 as the decimal
representation of the 8-bit byte 0011110 encodes the bit replacing the
middle bit of each contiguous block of 3 bits, on a bi-infinite tape
initially zero except for one bit, according to the following table.
000 0
001 1
010 1
011 1
100 1
101 1
110 0
111 0
0001000 then rewrites as
0011100
0110010
1101111 and so on.
Rules 30, 45, and a few others exhibit sufficiently chaotic behavior as
to be plausible candidates for rules with Turing-universal capability
when suitably initialized and interpreted. Most of the other rules
however exhibit such boring behavior as to make it very implausible that
they could sustain a coherent thought no matter how interpreted (though
some that are boring when started on ...0001000... might conceivably
perk up on more complex initial patterns).
The counterpart of this dichotomy in behavior for Harvey's "wild
conjecture" would be a representative sample of n's for which a small
fraction can be associated with much more chaotic behavior than usual in
a suitably canonical computation to determine which side of m*pi 2^[n]
falls in those cases where it falls extremely close to some integer
multiple of pi. Just as we know there are larger Turing-universal
cellular automata, we know there are more complicated trig formulas than
sin(2^[n]) for which such questions are indeed undecidable (by virtue of
embedding universal computation), making it easy for Harvey to encode
some association with large cardinals. Harvey's simple formula is the
counterpart of Wolfram's 256 three-bit rules: too simple to admit the
usual proofs, yet still with a potential for what one might call
"cryptic universality."
One difference is that whereas Stephen has a couple of candidates,
Harvey has not exhibited a single n giving rise to behavior that would
support the thesis that the occasional n is associated with necessarily
chaotic behavior in the determination of the truth of sin(2^[n]) > 0.
The choice of 2^[n] makes it very difficult to come up with any such
candidate; surely there are computationally more feasible yet
just-as-simple formulas where one could empirically search for
candidates. Is there some reason to suspect that (3/2)^n is no good for
this purpose, for example?
Another difference, this one in Harvey's favor, is that Stephen has yet
to come up with an unambiguous yes-no question as clear as Harvey's. In
the recent Wolfram 2,3 Turing Machine Research Prize competition,
Wolfram's goal seemed to be to offer a fame-and-fortune reward to anyone
who could find a sense in which the ostensibly chaotic behavior of a
certain very small Turing machine was universal. The prize was
eventually awarded for a novel solution that I argued at the time was
not technically consistent in the sense that the same method could be
used to establish the universality of behavior known to be decidable,
meaning that we have algorithms for deciding whether such behavior
always halts.
I felt that the fault lay with the organizer(s) of the competition, who
put the burden of judging technical consistency on the committee but
then unilaterally announced a winner before the committee had had time
to form an opinion. Everyone Wolfram chose for the committee was at
least 12 years senior to him, and youth tends to impetuosity (some more
than others), making this the sort of outcome that hindsight is great at
predicting. I feel that the committee would have benefited from a wider
range of ages so as to include the perspectives of a few leading
automata theorists, impetuous or not, who are actively engaged in
current research into automata and were not tenured decades ago.
Nearly two years after the announcement of the competition, I've finally
come up with a way of formulating what I think Wolfram was hoping to get
out of this competition in the way of intellectual content (i.e. besides
publicity for the book and WRI). In light of the simplicity of the
formulation I can only attribute the time it took to my dotage. Here's
a problem that I feel would have made sense for the competition.
Is the set of finite subwords of the configurations produced by Rule 30
recursive?
The configurations produced by Rule 30 are the bi-infinite words the
first few of which are enumerated in the fifth figure of Chapter 2 of
ANKS, the first four of which I gave above. These are nonzero in only
finitely many positions. One could lop off the infinite zero words at
each end to produce finite words, but the set of those would be
decidable since their length would tell you how far you needed to
compute to decide membership. Lopping off some of the nonzero part as
well (the meaning of "subword" here) potentially makes the problem
undecidable. If it did, that would be conclusive proof that Rule 30
encrypts a high degree of computing ability.
If the stronger result obtained that this set was r.e.-complete (what
recursion theorists used to call "complete" before it was joined by
other kinds of completeness such as NP-completeness), that would
similarly constitute conclusive evidence of the universality of Rule 30
in this stronger sense. (Turing-complete would be a slightly weaker
result, but the distinction is such a technical one that Turing-complete
would almost certainly entail r.e.-complete, as for that matter would
the even weaker result of mere undecidability.)
A better problem might be to find the smallest rule set having an
r.e.-complete set of sub-configurations (subwords of configurations).
If one fails to show that any of the 256 3-bit rules has an
r.e.-complete set of sub-configurations, move on to the 65,536 4-bit
rules. At 5 bits the problem should become quite easy, and I imagine
several people might come up with 4-bit solutions, in which case to
avoid sharing the prize one would be motivated to hit the 3-bit case
much harder.
A variant of the problem that might make it easier to find a universal
3-bit rule is to allow more complex transformations of the
configurations than simple truncation. "Any function with a recursive
range" would be about the limit here---"any recursive function" would be
too generous because a recursive function can have an r.e.-complete
range, this being a relatively clear-cut prototype of the sort of trap
the winner of the competition fell into.
This tightening of Wolfram's question puts it more on a par with
Harvey's wild conjecture, by removing the uncertainty as to the
formulation of universality. Harvey's conjecture (quantified over all n
for neatness, not just those less than 2^1000), has more of the flavor
of a yes-no question.
Yet something still seems to be missing, namely a precise notion of
"large cardinal." It seems to me that to make Harvey's question a
yes-no one to the degree I just did for Wolfram's Rule 30, one would
need to word it for a specific large cardinal, or at least a recursively
identifiable class of large cardinals.
Vaughan Pratt
More information about the FOM
mailing list