[FOM] irrational conjectures

[Vaughan Pratt]

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