Historical Ideas of Formal Uncertainty, and NKS Irreducibility

Jason Cawley

Wolfram Research

Session:  Philosophical Implications of NKS
 10:30am, April 23, 2004

This will be a talk about the history of ideas about limits to knowledge, placing NKS ideas on the subject in historical context, from ancient Greek and Enlightenment periods to Pierce and Popper. Different arguments have been advanced as to the scope and origin of such limits. NKS irreducibility preserves intuitions from some of them and revises others.

Introduction

I want to talk about the history of ideas about limits to knowledge, and place NKS ideas on the subject in some historical context.  Formal uncertainty has interested thinkers from ancient Greek and Enlightenment periods to Pierce and Popper.  Different arguments have been advanced as to the scope and origin of such limits.  In my opinion NKS irreducibility preserves intuitions from some of them and revises others.

NKS does not entail one philosophical view

I think the basic evidence of NKS is compatible with a number of traditional philosophic positions, and with a variety of commitments in contemporary discussions.  

I have my own opinions on a number of philosophy questions NKS touches on and Wolfram has strong views on many subjects.  But skeptical, critical, operational, pragmatic, realist and idealist readings of the basic story all seem to me possible.  (I can unpack that, perhaps in Sunday's Q&A session, if anyone wants).  I'm not going to pretend to settle such questions right now - though I certainly will tell you what I think, especially of the more recent arguments and positions.

Instead I want to look at previous understandings of formal limits to knowledge and then see how NKS moves around some of the issues or keeps them the same.  I am also just interested in how previous thinkers looked at these matters, without the benefit of NKS or other recent work.  So some of the following is going to be history - selective and speculative history at that.

What is a formal limit to knowledge?

What do I mean by a formal limit to knowledge?  I mean things like incommensurability, infinities, unpredictability, irreducibility; also whether reality and our ideas about it can or can't meet, for logical or structural reasons.  And asking about these things with an eye to what we can or can't expect to know, and how certain or qualified our knowledge might wind up being.   

A limit to knowledge is formal if it does not depend on a particular empirical state of affairs or e.g. the present power of our physical instruments.  A formal limit to knowledge may apply only to particular cases, to broader classes of various kinds (e.g. just some initial conditions, to clouds but not clocks, or all empiricals) , or to all possible objects of knowledge. 

In this context, formal modifies “limit”, rather than specifying the subject matter, though the two may be related.  Someone may argue for formal limits of knowledge of formal things or of empirical things or both.

I hope now you understand the sort of thing I will talk about.  With that understood, let's turn to some historical figures and a few of the particular formal problems they encountered.

Eratosthenes and Greek Mathematics

Before Eratosthenes - (Sqrt[2])

The Pythagoreans already knew the incommensurability of the sides of a right triangle, or in modern terms that the square root of 2 is an irrational number.  We understand that any sequence of rationals - including any digit expansion - trying to approximate the square root of 2, will not terminate.   While irrational, square roots were readily constructible geometrically.

N[(Sqrt[2]), 500]

Eratosthenes and Greek Mathematics

Eratosthenes' other results - Doubling the cube, geometric measurements

They encountered a bit more difficulty doubling the cube - in other words, finding a way to construct a line (as base of a new cube) of length the cube root of 3 times a given line.   Before Eratosthenes the problem had been reduced to finding 2 mean proportionals between two given lines, and others had particular solutions.  

He gave a mechanical geometric method, that is able to construct an arbitrary root of an arbitrary ratio - to me a nice sign of his attraction to general algorithms.  Essentially he exploited continuous translation of a rigid body, sliding a number of right triangles along one line making cords in mean ratio between two given lines.  What today we call the algebraic numbers were thus constructible for Eratosthenes.

He also used geometric methods to measure the circumference of the earth - to within 2-4%, we aren't sure exactly because we don't know what his unit of length amounted to precisely (an case of historical uncertainty about a purely conventional matter).  He also impressively got the distance to the sun to within about 10%, using data from eclipses collected long before.  He missed the moon, however.  His estimate of the distance to the moon was low by a factor of three.

He was an academic follower of Plato and ran the Alexandrian library in his day.  He is said to have composed a poem about the principles of astronomy, and (more on this below) to have produced a star catalogue containing the positions of exactly 675 stars.   Unfortunately all his own complete works are lost.  We only know his results at all from passages in other works that refer to them.

Eratosthenes and Greek Mathematics

The Sieve of Eratosthenes

And of course, he gave us the sieve - the algorithm for enumerating all the primes by striking out all numbers divisible by a prime less than the square root of a given number.  This is a method that can be applied mechanically, as successive multiples of each prime lie the same distance apart when the numbers are laid out in succession.  Only primes need to be used, and only up to the square root, since divisibility by a larger number would also imply divisibility by a lower one.

The method thus lends itself to a 2-D rather than a 1-D arrangement of the numbers to be considered.  A square of tiles laid out, from 1 to some prime across the top, with the next row representing addition of that prime to the number on the previous row.  Count across the top row to get through all the primes you need to test.  For each one, go through the pattern striking out successive numbers that are 2, 3, 5, 7... apart.  

Do we know he used the sieve this way?  Not remotely.  It is purely a guess.  If he did, how far might he have applied his algorithm, how many primes might he have discovered?  What set me wondering about this was the curious coincidence that the number of stars in his star catalogue is related to a number Plato makes much of in his Laws - 5040, 7 factorial.

7!

PrimePi[5040]

Divisors[5040]

71^2

PrimeQ[5039]

Prime[20]

EraPrimes  =  
        Table[ If[PrimeQ[71  j  +  i] == True,  1,  0],  {j,  0, 
            70},  {i, 1, 71}];

Show[Graphics[Raster[Reverse[EraPrimes]]],  
        AspectRatio -> 1];

ModernEraPrimes  =  
        Table[ If[PrimeQ[5039  j  +  i] == True,  1,  0],  {j,  
            0, 5038},  {i, 1, 5039}];

Show[Graphics[Raster[Reverse[ModernEraPrimes]]],  
      AspectRatio -> 1]

Continuity - from Hume to Pierce

From the development of calculus to Cantor's analysis of the continuum, formal uncertainty arguments centered on the idea of infinite divisibility or continuity.   Skepticism also raised philosophical objections to the knowability of the external world, as distinguished from math or logic, or as distinguished from immediate internal sense experience, or both.

Hume sought to banish infinite divisibililty by appealing to an different assertion, that our general ideas are copies of our particular sense experiences, with anything else we make of them basically added by us, without real justification.  In a footnote to chapter 12  of his "Essay Concerning Human Understanding", which he calls "a hint" and does not follow up, he states his hoped for corollary -

"...all the ideas of quantity, upon which the mathematicians reason, are nothing but particular, and such as are suggested by the senses and imagination, and consequently, cannot be infinitely divisible."

It would be charitable to call this an inadequate argument.  He has not shown that particulars are not infinitely divisible.  And his skepticism about all matters of fact, which he explicitly rests on the ability simply to imagine any apparent fact might be otherwise, does not leave him room to insist on it.  

He does not like continuity because it gives rise to paradoxes, but he has no other real argument against it.  Most of the simple paradoxes that bothered him have been handled successfully since, but others - associated with continuum rather than countable infinities - arose in their place.  Also, a man that does not blink at the propostion that we do not and cannot know whether the sun will rise tomorrow is not one to halt at paradoxes simply as such.  Incidentally, his suggestion about "translating" all general idea propositions to sense observations was attempted much later by logical positivism, but by now essentially everyone agrees, without success.

Wolfram argues for a reality in which only constructibles are physically realized (a version of Church's Thesis).  As such, he agrees with the basic position taken by Hume above, and does see our ideas of infinite divisibility as abstractions of our own.  But not because those ideas come with an inadequate "certificate" as to their origin, or because we are not allowed to use general ideas in our thinking.  Rather, if a physical theory succeeds in describing the world in purely discrete terms, Wolfram is prepared to regard it as simply right - a move which Hume's skepticism did not allow him.

In passing I note that Leibniz, sometimes thought of as a founder of information thinking, was fully committed to a continuous world, as some passages in his Monadology show.  Besides the calculus of course, he also made incremental progress on the longstanding formal issue of Pi.  Expanding a series, he gave Pi/4 as the limit of a simple infinite sequence of rationals, though one that converges very slowly.  It was not until 1888 that Pi was proved to be transcendental, beyond even the algebraic numbers.

Pierce  -  Continuum infinities

"A continuum is a collection of so vast a multitude that in the whole universe of possibility there is not room for them to retain their distinct identities..."

Pierce comes after Cantor and the basics of modern set theory.  Overall he shows an attractive intellectual pragmatism, in which the only essential thing is the ability of any process of reasoning to correct itself, to iterate.  But the formal innovations of his time were all on the side of extending the intuitions of analysis, leading him to such statements as "the continuum is all that is possible.  He understood the issue between continuous models and discrete ones to be equivalent to the decision between realism and nominalism -

"Are the continua real?"

And there is no doubt about where he comes out on the question.  The new continuum infinities of Cantor are the solution to all essential problems, and a vindication of realism about universals and idealism; continuity also explains freedom - 

"I will not trouble you with and disquisition on the extreme form of realism which I myself entertain that every true universal, every continuum, is a living and conscious being, but I will content myself with saying that the only things valuable, even here in this life, are the continuities".

It is a sobering historical mirror to look into.  We would find it hard to take seriously.  But have similar claims sometimes been advanced for the bright new formal star in our firmament, computational universality?  The joke about Penrose was that he is so smart, there are only two things he does not understand - consciousness and quantum gravity.  So he wrote a book explaining that they must be the same thing.

I am being hard on Pierce but I like him on method and other subjects.  His one great rule is "do not block the way of inquiry", confident in reason's power not to see the truth instantly, but to correct itself.  And it is a fair question, one that we may have hunches on or large philosophical or methodological commitments about.  But we can't honestly say it is decided.  Wolfram acknowledges that doubts about Church's thesis will only be resolved by a successful discrete theory of fundamental physics.

Pierce understood continuity as relational generality, as arising from the idea of possibility space.  NKS simple rules deal with finite or at most countable systems, in terms of elements, initial conditions, and steps.  And the physically realizable set of states may well be finite or countable, fitting Church's thesis.  Perhaps we can see a place for higher ordinals in this - the space of all possible simple rules.

Popper - Clocks and Clouds, Chaos and SR

Popper gave us the criteria of falsifiability, enjoining us to stick our necks out and make claims about the world.  He deserves great credit for showing that Hume's attack on inductive method was unfounded, that it was justified as trial and error.   Pierce deserves credit for stressing the same self correcting character of reasoning.  Between them, I think they have largely freed us from the philosophic straitjacket of skepticism and positivism, without sacrificing anything essential in scientific methods.  

While trying to make a case for indeterminism, Popper also gave us the distinction between clocks and clouds, meaning ordinary physical-mechanical systems that just happen to be predictable or that don't happen to be.   This was a service because it removed confusion about whether the fundamental distinction concerned other contrasts - living vs. mechanical, free vs. determined, historical or human vs. natural, etc.  Popper insisted that unpredictability invades the hard sciences.

But he left some confusion about whether it only arose in the study of physical systems, external or empirical realities, whether the problem arises from getting outside our heads.  He was limited in the arguments he made in favor of his thesis of indeterminism - but in some ways quite modern.  He used arguments from sensitive dependence on initial conditions, from special relativity, and from supposed paradoxes of self-reference in the specific form of self prediction problems.  Of these his sensitive initials argument was the soundest as he presented them.  The self prediction argument, which he considered the strongest, was poorly formulated by him, I believe because he missed the critical point in an example suggested to him by Alan Turing.

Popper's version of the sensitive dependence argument was based on the 3 body problem, in Hadamard's formulation (uncertainty in an initial angle).  The essential mechanism is that explained in the NKS book - small differences on the first few orbits are magnified in later ones.  By now this is a well known argument, and it does what he needs it to do.  It shows that some physical systems are inherently so unstable that predicting them is impossible without perfect information.  

His special relativity argument is unconvincing.  Essentially, he notices the possible import of new information or influences from beyond the existing past light cone of a system, as time advances.  He then notes that to possess perfect information about the entire past that could influence a point, an observor must be in the future of the event he has the exhaustive information about.  However, the argument fails to show what he want it to show, because he does not establish that prediction is only possible with such exhaustive information.  He simply presents that as though it is a grand concession "I'll give you lots of information and you still won't be able to predict", then using how long it might take to get all to advance his own case.  It is not a concession, in other words.  And e.g. if the imported information is a strictly limited, stationary heat bath of low energy photons (starlight or microwave background), it is implausible that makes any difference for practical predictability.  At best, it makes a glancing hit on a straw man version of Laplace.

Popper II - Self Prediction vs. Irreducibility

His most interesting construction is his apparent paradox of self prediction.  Overall he might have a case that self-prediction problems of suitably qualified systems - newly acquired knowledge might influence what they do, and being new in the future, that knowledge is not available now.  And what he should say but doesn't is that computationally universal systems will generate such paradoxes, at least up to speed up rules or special initials cases.   Turing suggested to him the idea of illustrating his problem with deterministic machines, as Popper reveals in a footnote thanking him for the suggestion.

But although I like Popper on method and there is a possible good argument he might make, he does not in fact make it - in "the open universe" chapter on the impossibility of self prediction.  Essentially, after elaborately setting up the problem but not specifying the formal power of the predictor and predicted systems (just, they have the relevant laws and logic etc), he forces on his predictor system the same initial condition as the predicted one.  He does not notice that he has thereby assumed the conclusion.  Because by construction they are deterministic machines.  When their initial condition is specified, so is their behavior.  

But there is in general no reason the predictor system needs to emulate the predicted one, by walking through its states "one to one and onto".  Imagine both are universal and the predicted is currently trying to emulate a clock-like simple behavior.  The predictor - with exactly the same resources - might detect this, short cut the evolution, predict the outcome with a simple mod 2 rule or some such, and give the result.  Never visiting the intermediary states of the other machine.  Nowhere in the problem has Popper required that the predictor machine be able to predict every possible behavior of the predicted.  And it is simply false that a sufficiently sophisticated machine cannot predict the behavior of an equally sophisticated one, when the latter is doing something inherently predictable enough.  Predictable does not adhere to a machine, but to whatever it is presently doing - the machine plus its initial condition, in this case the task it has been set.

Popper only fails to notice this by his "assumption" that the predictor starts in the same initial condition - which begs the question, since it necessarily implies the same outcome as well.   But it is highly instructive to see where the attempt breaks down.  It is not by failing to require the predictor to predict anything the predicted might do.  The real issue is whether the actual evolution the predicted machine is going through, it compressible or not.  If it cannot be done faster than by one to one and onto mimicking of its internal trajectory, then the argument works.  If it can be done faster, then the argument fails.  Predictability - by the same thing or by something else - turns on the issue of computational reducibility.  Not self reference.

I suspect Turing meant Popper to refer to universal systems, specifically.  And to something like all their possible behaviors.  But the unpredictability of that does not turn on self reference.  And Popper wanted and needs not an all possible behaviors result, but more like an any behavior result.  Which just isn't so, unless the system being predicted - whether it is itself a predictor emulating a third system or not - is doing something irreducible.  Clocks and clouds happen even on the formal side.  He clearly understands that point as an empirical matter.  But he does not think of the cloud as a more involved bit of logic.  He doesn't see the commensurability between them.

This brings us to point I want to end on.  NKS has turned the basic epistemological problem, from an inside to outside gap that is always present, to a rule to behavior gap that is present only some of the time.  A rule as regular as a clock is not like rule 30.   They do not differ because one is empirical and one is formal or logical.  They do not differ because one is deterministic and the other stochastic.  They do not differ because the initial conditions are known for one but not for the other.  They do not differ because they have a different ordinal number, finite or countable or continuum.  One is just plain simple, and the other just plain isn't.  One is reducible by analysis to a much simpler subsystem, isomorphic to the overall behavior of the whole thing, and requiring far less computational effort.  And the other is not.  Irreducibility arises, when it does, for purely formal reasons.