Monday 4 December 2017

Toomas Karmo: Part T: Philosophy of Perception, Action, and "Subjectivity"

Quality assessment:

On the 5-point scale current in Estonia, and surely in nearby nations, and familiar to observers of the academic arrangements of the late, unlamented, Union of Soviet Socialist Republics (applying the easy and lax standards Kmo deploys in his grubby imaginary "Aleksandr Stepanovitsh Popovi nimeline sangarliku raadio instituut" (the "Alexandr Stepanovitch Popov Institute of Heroic Radio") and his  grubby imaginary "Nikolai Ivanovitsh Lobatshevski nimeline sotsalitsliku matemaatika instituut" (the "Nicolai Ivanovich Lobachevsky Institute of Socialist Mathematics") - where, on the lax and easy grading philosophy of the twin Institutes, 1/5 is "epic fail", 2/5 is "failure not so disastrous as to be epic", 3/5 is "mediocre pass", 4/5 is "good", and 5/5 is "excellent"): 4/5. Justification: Kmo had time to develop the necessary points to reasonable length.
 
 
Revision history:
 
All times in these blog "revision histories" are stated in UTC (Universal Coordinated Time/ Temps Universel Coordoné,  a precisification of the old GMT, or "Greenwich Mean Time"), in the ISO-prescribed YYYYMMDDThhmmZ timestamping format. UTC currently leads Toronto civil time by 5 hours and currently lags Tallinn civil time by 2 hours.

  • 20171206T2251Z/version 3.0.0: Kmo finished converting his finegrained outline into coherent full-sentences prose. He reserved the right to make tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 3.0.1, 3.0.2, 3.0.3, ... . 
  • 20171205T1953Z/version 2.0.0: Kmo uploaded a finegrained outline, itself duly polished. He hoped to convert this at some point or over (not at the moment easily predicted) in the coming 26 hours into coherent full-sentences prose). He planned to do the work incrementally, uploading a bit of the conversion at a time. 
  • 20171205T0238Z/version 1.0.0: Kmo uploaded a mere coarsegrained point-form outline.  He hoped, either (1) at some point in the next 3 hours or else (2) (less ambitiously) at some point in the next 16 hours but not in the next 3 hours, to finish converting his coarsegrained point-form outline into a finegrained point-form outline. Further, he hoped soon after completion of that conversion to find the three or four additional hours needed for upgrading his finegrained outline into coherent full-sentences prose.

 
[CAUTION: A bug in the blogger server-side software has in some past months shown a propensity to insert inappropriate whitespace at some points in some of my posted essays. If a screen seems to end in empty space, keep scrolling down. The end of the posting is not reached until the usual blogger "Posted by Toomas (Tom) Karmo at" appears. - The blogger software has also shown a propensity, at any rate when coupled with my erstwhile, out-of-date, Web-authoring uploading browser, to generate HTML that gets formatted in different ways on different downloading browsers. Some downloading browsers have sometimes perhaps not correctly read in the entirety of the "Cascading Style Sheets" (CSS) which on all ordinary Web servers control the browser placement of margins, sidebars, and the like. If you suspect CSS problems in your particular browser, be patient: it is probable that while some content has been shoved into some odd place (for instance, down to the bottom of your browser, where it ought to appear in the right-hand margin), all the server content has been pushed down into your browser in some place or other. - Finally, there may be blogger vagaries, outside my control, in font sizing or interlinear spacing or right-margin justification. - Anyone inclined to help with trouble-shooting, or to offer other kinds of technical advice, is welcome to write me via Toomas.Karmo@gmail.com.]


We have been examining the notion of an infinite bit sequence, in the sense of a sequence possessing a first binary bit, a second binary bit, and so on, and yet possessing no last binary bit.  I have already made some rather formal remarks, in almost a quasi-mathematical sense, on the troubling (because definition-recalcitrant) concept of a random infinite bit sequence. It is advisable to proceed through a quite long set of further formal remarks in this installment ("Part T"), and at the very least in some initial portion of the next installment ("Part U"), before finally standing back and attempting to draw philosophical morals about our current topic of philosophical concern within the Geography of Mind, namely the topic of thinking-about-being. 

****

It is convenient first to introduce some shorthand. Call an infinite bit sequence "Turing-orderly", or still more briefly "T-orderly", if it is the output of some never-halting Turing machine. Call an infinite bit sequence "Intra-Turing-orderly", or still more briefly "IT-orderly", if it both (a) is in some sense orderly, and (b) is not the output of any never-halting Turing machine. As noted in "Part R", from 2017-11-20 or 2017-11-21, a bit sequence - I called it the "Specially Troublinbg Orderly Sequence" or "STOS" - which itself sets out the entire sequence of never-halting Turing machines (given an encoding scheme which maps all Turing machines one-to-one onto the set of positive integers) (a) is in a reasonable sense "orderly", and yet (b) (by the Turing-insolubility of the Halting Problem) fails to be T-orderly. The STOS, then, is an example of an IT-orderly, as opposed to a straightforwardly T-orderly, infinite bit sequence. - I use the term "infra" to convey the idea that such a troubling sequence is orderly indeed, and yet attains only a level of orderliness "below", or "inferior to", the level of orderliness attained by a sequence which is straightforwardly T-orderly, or in other words is straightforwardly machine-computable. 

****

Whatever it may be for an infinite bit sequence to be random, such a sequence can at any rate not, on the strength of our once performing any one finite single-sample statistical test, be either proved random or proved orderly. Take any one finite sample, no matter how extensive and how cunningly selected, from a given infinite bit sequence (call it "Sam"). The outcome of any statistical test on the Sam-sample will be at best (a) subjectively, nonrigorously, suggestive of true randomness in Sam, or else (b) at best subjectively, nonrigorously, suggestive of true orderliness in Sam.

Regarding possibility "(a)": No matter how random-seeming a single sample of N bits out of Sam may be, it is possible that Sam as a whole is of the form Z Z Z Z ..., where Z is some (perhaps very random-seeming) finite bit sequence. For example, the finite bit sequence 110100101 looks rather random, and yet the infinite sequence 110100101110100101110100101110100101110100101110100101... (the result of repeatedly concatenating the finite string 110100101 to itself) is orderly. If Sam is a sequence of the repetitious form Z Z Z Z Z ..., then Sam is indeed not just orderly, but even T-orderly.

Conversely, regarding possibility "(b)": No matter how orderly-seeming a single sample of N bits out of Sam may be, if any random sequences exist at all, then it is possible that Sam is himself also random. For let Roger be the posited random sequence. The N-bit sample taken from Sam might, to be sure, have been selected ingeniously. The finite Sam-sample need not be anything as gauche (in both senses of that Gallic reproach) as a mere finite initial segment of Sam. Nevertheless, the sample cannot reach further than some particular bit in Sam, say Sam's kth bit (where k might, admittedly, be larger than N). For all the sample can tell us, it is possible that from his (k+1)th position onward, Sam is a mere copy of the (k+1)th, (k+2)th, ... bits of Roger. If Sam's bits eventually fall into a mere imitation of Roger's bits, then no matter what the actual definition of randomness might turn out to be, Sam must be deemed random.

****

In place of taking a single finite sample from Sam, one might now try, in this quest for the Holy Grail which is a definition of randomness-of-Sam, taking the infinite set of finite-samples-from-Sam meeting some appropriate condition. Consider, for example, a test constructed in terms of all finite initial segments of Sam. If Sam is 1011100010010111011..., then the selected finite samples from Sam become on this proposal 1, 10, 101, 1011, 10111, 101110, ... . One might hope that if Sam is truly random, the ratio of 1-bits to 0-bits in the successively larger finite samples "eventually approaches unity", in some formally definable sense of "eventually approaches". This would, after all, mirror the informal way in which people might satisfy themselves that a given coin is fair, as a preliminary to some envisaged game of coin-tossing. Such prospective gamers might make many tosses. They might check to see that as the number of tosses becomes large, the number of heads starts differing only slightly from the number of tails. If after, say, 100 trials, there are 48 heads and 52 tails, they might feel happy enough. Conversely, if after 100 trials there are 91 heads and just 9 tails, the prospective gamers would be liable to accuse their candidate coin of bias.

A condition along the lines proposed cannot, however, be sufficient, since the very-orderly Sam which is 10101010101010101010... would pass it.

Further, a condition along the lines proposed cannot be necessary, at any rate if there exists any random bit sequence at all. For suppose, hypothetically, that random bit sequences do exist. Let Roger be a random bit sequence. Roger can be used as a guide for constructing a Sam that harbours progressively more enormous unbroken finite runs of 0s. Since I obsess over the Dark Ages (pondering Latin with gusto when I face the past, and reading such contemporary English-language doomsters as John Michael Greer and Dmitry Orlov with equal gusto when I face the future), I like to think of this in terms of Barbarian Armies - "Armies of 0-bits".

Here is Sam, looking eminently orderly, looking ever-so-Roman, in all the finite initial segments so far inspected. So far, each finite initial segment has consisted entirely of 1s. But from the jth bit of Sam onward, we encounter a great, though as it eventually turns out finite, Army of 0-bits. The sinister parade of 0s does, I stress, eventually end. Alas, however: it does not end until it is the 0-bits that predominate overall, in the entire up-to-this-point start-from-the-extreme-left finite sampling of Sam. Perhaps we are happy enough over the orderly appearance of Sam's first 5 initial segments, and get a rude awakening only completing the inspection of Sam's 6th through 30th bits. In our growing despondency and alarm, we do find as the 31st initial segment 1111100000000000000000000000001. With Alaric, so to speak, at last withdrawing, and with the Roman Senate convening once again, we settle down to a long epoch of PAX ROMANA. (For instance, the 50th initial segment proves to be, to our joyous relief, to be
11111000000000000000000000000011111111111111111111.) For a long, long time, Sam is in a state of pleasing 1-itude. As for the 50th initial segment, with its unbroken string of right-end 1s, so also for the 51st, the 52nd, ..., right up  to perhaps the 674th. But just as our complacency assumes the proportions of ARROGANTIA SVPERBIAQVE, up slouches another Army of Zeroes. Now it is not, say, Alaric, but the markedly more dismal Attila. This fresh Army lasts so long that Sam's finite initial segments seem to be practically "Zero City", with only the tiniest fraction of their bits set to the pleasing 1. For Attila is dauntingly long, perhaps comprising a string of fully 9837 1s. At long last Attilla withdraws. The Roman Senate convenes again, and now there are lots of 1s, in fact two million of them. But as our civic complacency grows and grows (GAVDEAMVS, O CIVES, NVNC ETIAM VIGINTI CENTENA MILLE HABEMVS), in slumps Theodoric, with an Army of Zeroes that dwarfs even the horrors of Attila (and so on, and so on).

It might be objected in desperation that some regularity is still lurking, kinda-sorta, perhaps-perhaps, "at one significant level", namely in the timing of those successively longer barbarian parades. Without, however, scrutinizing the possible partial merits of the desperate objection, I note that it cannot in the final analysis prevail. I dismiss it with the final-analysis retort that the time between successive barbarian incursions might not only get longer and longer, but might even grow - within the admitted, perhaps quasi-orderly, constraint of strictly monotonic increase - in a random way, as guided by that fount of barbaric nastiness (that governing FONS ET ORIGO MALORVM) which is Roger.

****

Richard von Mises (1883-1953) tried to characterize random infinite sequences in terms of "proper selections". His idea was, I believe, that it either it was necessary or it was sufficient, or perhaps even that it was both necessary and sufficient (I have not investigated this history-of-ideas topic properly) for progressively larger "properly selected" finite subsequences from a truly random Sam to have their count-of-1s get in some formalizable way pleasantly close to their count-of-0s. His idea was a generalization of the more limited idea, dismissed above, of inspecting just Sam's finite initial segments. We are now not to be so naive, or gauche, as to take all and only the finite initial segments. Rather, under the guidance of von Mises, we are to take larger and larger "proper" finite selections.

The (surely nonrandom) Sam which is 101010101010101... looks distressingly random if we take merely Sam's finite initial segments, comparing in each of these infinitely many cases the respective accumulated finite populations of 1s and 0s. Such a selection is, however, for von Mises in some sense "improper". The (surely random) Sam which is Long PAX-ROMANA Epochs-of-1 interpunctuated with Terribly, Hideously Protracted Visigothic-Ostrogothic-Hunnic-Lombardic incursions of 0s (the times of the infinitely many interpunctuations being themselves cunningly Roger-regulated) looks from the standpoint of finite initial sequences rather orderly. It is, for much of the time, rather overweighted in 1s, and the overweighting never does go away for good. But such a selection, which may betray us into giving the over-optimistic verdict "orderly infinite sequence", is again, for von Mises, in some sense "improper".

Everything now turns on the feasibility of defining, in formal terms, the key concept of a "proper selection". I have the impression that von Mises tried hard, over his long and distinguished career at the mathematics-philosophy-physics interface. The consensus nowadays seems, however, to be that his efforts, however valiant, failed.

****

Now I turn to a contemporary attempt at characterizing randomness, inspired by a relevant idea of Kolmogorov's for finite sequences. I shall be suggesting that this contemporary attempt, while still leaving a kind of gap, does enjoy a success which the Gods of Mathematics denied in bygone decades to von Mises. Specifically, I shall be suggesting that the Kolmogorov-inspired contemporary attempt, while failing to give a necessary condition for randomness, does deliver a plausible sufficient condition. The attempt is (I gather) associated with the three contemporary workers Martin-Löf, Levin, and Schnorr.

Kolmogorov inadvertently launched the contemporary randomness-of-an-infinite-sequence work by posing a deep question regarding mere finite sequences. Although any finite sequence is the output of some Turing machine, some finite sequences are intuitively more orderly than others. An unbroken string of a billion (a thousand million) 1s, for instance, is intuitively more orderly than a string of a billion bits, all of them 1 except for a lone 0 in the second place. The latter is in turn intuitively more orderly than a string of a billion bits, all of them 1s except for 0s in the 2nd, 3rd, 5th, 7th, 11th, 13th, 17th, 19th, 23rd, ... places (in general, with 0s in all and only the pth places, for the prime numbers p in the set {2, 3, ... , 1 billion}).

One's first inclination is to say, "Well, that is a mere subjective impression, a worthless intuition. From a mathematical standpoint, any sequence comprising (say) one billion bits must be just as orderly as any other." But I gather that Kolmogorov asked, in essence, the question, "How long is the (finite) internal program table for each of the various Turing machines generating the various billion-bit sequences?"

A rather small Turing machine suffices to generate the all-1s billion-bit sequence (One could somehow specify a counted loop, to execute exactly a billion times. Surely this can be done by conferring on the machine an internal program table of far fewer than a billion lines.)

A slightly more elaborate Turing machine seems needed for generating the second-cited billion-bit sequence. Now we might well use a counted loop, as before, while running the loop just 999,998 times. This slightly more elaborate machine would be programmed to start its loop after first both printing 1 in its Boot Square and printing 0 in the square immediately to the right of its Boot Square.

For the third-cited billion-bit sequence, a more elaborate Turing machine seems necessary, although I would imagine its still having far fewer than a billion lines in its program table. Perhaps a reasonably economical such machine will actually discover all the prime numbers in the set {2, 3, ... , 1 billion}, say by running the Sieve-of-Eratosthenes algorithm, and on the strength of its numerous discoveries then work out where to write its numerous 0s.

The Kolmogorov idea is that as we come to the "very disorderly billion-bit sequences", such as might be procured by running a device resembling John Walker's random-bits server (https://www.fourmilab.ch/hotbits/; this was mentioned here in "Part P", from 2017-10-23 or 2017-10-24), the program table begins to resemble in its now-formidable length the target billion-bit sequence itself. If we cannot discern a pattern in the billion bits, we will have to tackle the programming task by sheer brute force, instructing the machine to "print this in the Boot Square, then that in the next square to the right, and then such-and-such in the following square", where each "this" and "that" and "such-and-such" is the desired bit (and so on and so on, for a billion or so wearisome, plodding lines of internal Turing-machine program table).

To be sure, an objection of a kind does suggest itself. Could the length of a sequence-outputting machine program depend in some conceptually crucial way on the specific prior selection of deteriministic machine architecture? Could it be that the third of my cited billion-bit sequences, for instance, is compactly computable by a deterministic machine of some suitably clever, not-quite-orthodoxly-Turin, hardware design - say, one incorporating in its underlying hardware, as opposed to its internal program table, something to deliver the effect of a lookup table listing the first few hundred million primes?

I suppose (without having gone into this at all carefully) that we could now somehow appeal to the notion of a "legitimate machine", thereby blocking such ad-hoc things as an internal, hard-wired, prime-number lookup table. Maybe (say I - without, I stress, having gone into this at all carefully) we could demand that any "legitimate machine" be capable of being programmed to act as a Universal Machine (in the sense of last week's Universal Turing Machine "U"), and that it in some sense contain "no proper submachine of itself" capable of being thus programmed.

We could also (say I, without having gone into this at all carefully) put the central, philosophical-as-distinct-from-purely-mathematical, idea in terms of a challenge. Last week, I noted that the historical Prof., A. Turing sought to capture the philosophical essence of computing, through a "Thesis" which I worded thus: any computation that could be performed (perhaps efficiently, i.e., perhaps in some very small number of clock cycles) on anything reasonably called a "deterministic computer" could be performed also (perhaps less efficiently, i.e., perhaps in some larger number of clock cycles) on a Turing machine. 

I added the following comment last week:  It is impossible in principle to prove the "Thesis" through mathematical argument, since its notion of "anything that could reasonably be called a 'deterministic computer'" is not mathematically formal. Nevertheless, no examination of the powers of any particular deterministic computing-machine architecture, from the time the Thesis was proposed (and it goes way back, to before the war, I think in fact to a 1936 November address by Prof. A. Turing to the London Mathematical Society) right up to the present day has succeeded in delivering any counterexample.

A similar situation perhaps holds for Kolmogorov. As one might perhaps phrase it: For anything that could be called a "Kolmogorov-legitimate deterministic computer" K, K imposes a "measuring of disorderliness" on billion-bit sequences, such that the generating of the progressively "intrinsically more disorderly" billion-bit sequences requires progressively longer internal K program tables. 

An appropriate comment on this week's "Kolmogorov Thesis", in the spirit of last week's comment on the "Thesis" which last week I associated with Prof. A. Turing, would then be the following: It is impossible in principle to prove the "Kolmogorov Thesis" through mathematical argument. Nevertheless, the mathematical community may legitimately be challenged to find plausible counterexamples.  Nobody from Kolmogorov's time (back in the Cold War) right up to the present day (even 2017 is now almost over) has succeeded in delivering any duly publicized counterexample. 

(Well, folks, you will note the advisability of e-mailing Toomas.Karmo@gmail.com should it turn out, contrary to what I think is the state of the literature, that someone has actually published a counterexample to what I am calling the  "Kolmogorov Thesis".)

Provisionally accepting the Kolmogorov Thesis, we may now proceed in the spirit of the already-mentioned contemporary workers Martin-Löf, Levin, and Schnorr. From a hasty glance at just a couple of pieces of encyclopedia-level writing (I think both in Wikipedia and in the multivolume 1990s Routlege encyclopedia-of-philosophy), I gather that the idea (henceforth, the "The K-Idea", to give Kolmogorov his due) is as follows:

  • Inspect, not in von Mises' spirit "properly selected" finite samples from Sam, but in a more gauchely robotic spirit simply each of Sam's successively longer finite initial segments. 
  • It might be that for some N, each finite initial Sam-segment of length j greater than or equal to N proves rather strongly Kolmogorov-orderly. (This would be trivially the case if Sam was the infinite sequence 11111... . It would also be the case, although less trivially so, if Sam was orderly in a kind of prime-numbers way - consisting, for instance, entirely of 1s, except that for every prime p, Sam has a 0 in his pth position.)
  • It might be that for some N, each finite initial Sam-segment of length j greater than or equal to N proves rather strongly Kolmogorov-disorderly (through requiring - I reiterate - in some duly formalizable sense of "not significantly", a Kolmogorov-legitimate internal machine program table with not significantly fewer than j entries).
Although these are not the only possibilities,  I may as well stop here. Let us call the possibility sketched in the last of these three bullet points a situation in which "Sam's finite initial segments eventually become Kolmogorov-disorderly". I gather that this is the possibility to which Martin-Löf, Levin, and Schnorr direct special attention. Have we in this third bullet point, then, a condition (a) necessary for randomness-of-Sam, and (b) sufficient for randomness-of-Sam?

Regarding "(a)": as far as I can see, necessity fails, for reasons once again connected with barbarian incursions. (But I am subject to correction by readers: please e-mail Toomas.Karmo@gmail.com as appropriate.) Sam might be random in a cunning way, making him from a K-Idea standpoint look non-random. Perhaps Sam starts off with a long unbroken string of 1s. Eventually Alaric comes slouching in, with his dispiriting army of 0s. So many 0s are there in this First Sack of Rome - so greatly do they overwhelm the admittedly initially-plentiful 1s - that any Kolmogorov-legitimate machine computing the finite initial Sam-segment that ends with the First Sack has a rather easy time of it, and therefore is rather small in comparison with the big finite bit-string it is tasked with computing. (That finite initial segment is dominated, thanks to the so-protracted Sack, by 0s. A lot of the programming can therefore be achieved in a terse way, by directing the Kolmogorov-legitimate machine into a counted loop.)

Now come, again, lots of 1s, and the requisite Kolmogorov-legitimate machines get a bit longer in proportion to the lengths of the successive finite initial Sam-segments.

And then, perhaps a very, very long time later, it is Theodoric's turn.

So, as far as I can this week see, things never do settle down: Sam is cunningly random, and yet our successive parade of successive Kolmogorov-legitimate coumputing machines never does stop featuring a machine with some dramatically compact internal program table (compact, that is, in comparison with the long task-required finite initial Sam-sequence).

Regarding "(b)": Here things look happier. I cannot at least find an objection. My sole intelligent, or semi-intelligent, remark is that one would ultimately entertain the pious hope of a proof, perhaps through some outright exhibited construction, that the Kolmogorov condition can be met. One would hope actually to see some recipe (or, failing that, some recipe outline - some sketch) for building a Sam whose successive initial segments eventually settle down into a reliable, steady state of Kolmogorov-disorderliness.

The situation is here to me (I admittedly write as a rank amateur) a bit like the situation with that "field", in the abstract-algebra sense, which is the reals. We have the abstract algebraic definition of a field - as at, e.g., https://en.wikipedia.org/wiki/Field_(mathematics) - and we have (let us say) some professorial assurance, or even have ourselves mastered some formal proof, that the rationals, with the usual multiplication and addition operations, and with the usual additive and multiplicative identity elements and inverses, satisfy the clauses of the definition. Can we now proceed in confidence to build up the elaborate edifice of, say, univariate differential-and-integral calculus, as a topic within the real numbers?

We cannot. We must first prove that the reals themselves satisfy the clauses in the definition of a field. This takes lots of work, in which the reals get constructed as convergent infinite sequences of rationals (or, alternatively, as Dedekind cuts within the rationals), and in which those constructed objects are themselves proved to satisfy the abstract, algebraic, field-definition clauses upon getting endowed with plausible definitions of addition, of multiplication, of additive and multiplicative identity, and of additive and multiplicative inverse. Until this work is performed, we cannot be free of the nagging fear that somehow, at some hard-to-expose level, the concept of real numbers, with their completeness property that renders calculus possible (in one statement, "Every nonempty set of reals bounded above has a least upper bound"), harbours a contradiction. (In classical antiquity, Zeno already worked hard along something like these lines. The modern consensus, to be sure, is that Zeno's arguments fall to rebuttals. But in coming centuries, might some fresh Zeno not emerge, defying all efforts at rebuttal - thereupon destroying the intellectual edifice of our current mathematical physics, which has calculus in its lower floors?) - That is the work to which a group of us first-years were exposed at Dalhousie University, in Nova Scotia, in the winter semester of 1971, under Prof. Max Edelstein (1917-2003). I further believe the (formidable) work has traditionally been made available to visitors of mathematics libraries from a textbook of that particular Landau who is from Germany, as distinct from Russia (not the much-mourned Soviet Lev Davidovich Landau (1908-1968), but the also eminent, and historically somewhat earlier, German, Edmund Georg Hermann Landau (1877-1938)).

Even the professional mathematicians do have from time to time to live in the pious hope of some so-desperately-needed construction simply emerging. People were doing calculus, and with it mathematical physics - and perhaps even, for all I as an amateur know, attaining some degree of rigour - before the reals finally got constructed out of the rationals.

- Well, actually, I can supply a still more terrifying example of professional "pious hope". Even the most squalid, beer-swilling, Homer-Simponesque engineers - on the University of Toronto, those exuberant party-goers who inhabit the raucous eastern side of St George Street, in their various noisy little barracks, as the physicists look down on them from the west side of St George, from soberly silent, suitably lofty, perches in their Burton Tower - will pretty soon in their work have to invoke "Fubini's Theorem". Fubini's is the theorem that permits the interchange, at least under any conditions likely to be satisfied in the problems arising within mainstream physical science, of the limits of integration in those nested univariate integrals which become the practical tool for simplifying the Riemann integral of a multivariate function mapping n-tuples of reals into the reals. Everyone, from Homer Simpson in first- or second-year engineering upward, has to interchange limits of nested univariate integrals in practical work. So when did Fubini construct his so-mission-critical proof? Hold onto your seats, everyone. It was not in the floruit of Newton and Leibniz. It was not in the (Victorian) floruit of Dedekind and Weierstrass. If https://en.wikipedia.org/wiki/Fubini%27s_theorem has the history right, the proof came so late that the parents of millions of people still living were born after Fubini constructed it, when Queen Vicky was already some years dead - so late as 1907.

****

It is now time to set homework.

I first introduce further formalities. Although these are of my own devising, they are in their way rather reminiscent of von Mises, as described above.

We have already divided the infinite bit sequences, exhaustively and disjointly, into the random and the orderly (while, admittedly, leaving open the question whether random bit sequences exist at all). The universe of orderly bit sequences we have divided into the Turing-orderly (the "T-orderly") and the "less-than-Turing orderly", or "infra-Turing orderly" (the "IT-orderly"). - Further, we have used the Halting Problem literature to show that not only the set of T-orderly infinite bit sequences, but even the so-subtle set of IT-orderly infinite bit sequences, is nonempty.

It is now time to introduce further terminology. I introduce it, as I say, in something of a von Mises manner.

Consider those random infinite bit sequences Roger (supposing, for the moment, that at least some random infinite bit sequences do exist) having the following property:

  • Every infinite subsequence of Roger selected by some Turing machine or other is itself random. (In different words: "Every T-selected infinite subsequence of Roger is itself random.")
For possible convenience, I will call any such Roger a "Green Roger", and the set of Green Rogers "Greenland".

Consider, next, those random sequences Roger having the following contrasting property:

  • Every infinite subsequence of Roger capable of being selected from Roger in some orderly way, but incapable of being selected in a Turing-orderly way from Roger, is itself random. (In different words: "Every IT-selected infinite subsequence of Roger is itself random." - If h1, h2, h3, ... are the successive integers denoting never-halting Turing machines, as in these present blogger-cum-blogspot discussions of the Halting Problem, then one IT-selected infinite subsequence of Roger will be the infinite sequence created by taking Roger's h1-th, h2-th, h3-th, ... bits.) 
For possible convenience, I will call any such Roger a "Red Roger", and the set of Red Rogers "Redland".

Finally, consider those random sequences Roger having the following, definitionally more constrictive, property:

  • Every infinite subsequence of Roger capable of being selected from Roger in any orderly way at all (be that way T-orderly or, by contrast, be it merely IT-orderly) is itself random.
Any such Rogers would have to be both Red and Green. It is therefore convenient, in this season of Advent, to call any such Rogers "Yuletide Rogers", and the set of such both-Red-and-Green Rogers "Yule Country".

Finally, it is convenient to call that part of Greenland which lies outside Redland (equivalently, which lies outside Yule Country) "Extreme Greenland", and to call that part of Redland which lies outside Greenland (equivalently, which lies outside Yule Country) "Extreme Redland".

A first homework question is now this: what, if anything, can we assert, or even conjecture, regarding the emptiness or nonemptiness of Extreme Greenland, Extreme Redland, and Yule Country - and, for that matter, regarding the emptiness or nonemptiness of Greenland (this is definitionally broader than Extreme Greenland, definitionally overlapping, as it does, Redland) and about the emptiness or nonemptiness of Redland (this is definitionally broader than mere Extreme Redland, definitionally overlapping, as it does, Greenland)? What, in other words, if anything, can we assert or conjecture regarding the nonemptiness of the five just-mentioned bits of terrain, under the governing assumption that some random sequences of some kind or other do exist?

A second homework question can be set up more quickly. Kolmogorov has, as noted this week, apparently given a sense to the question "How orderly - just feebly orderly, or not-so-feebly-orderly - is a given finite bit sequence?" What sense, if any, might now be given to such terms as "feebly random infinite bit sequence", "random infinite bit sequence which is not-so-feebly random", "random infinite bit sequence which succeeds in being vigorously random", and the like?

Finally, here is a third homework question. If any random infinite bit sequence Roger exists at all, then there are such things as "infinite random bit sequences differing only trivially, i.e., only in orderly ways, from Roger himself". For suppose, hypothetically, that random bit sequences do exist, and let Roger be one of them. Let Roller be the result of rolling each of Roger's bits over, in the sense that Roller has 1 wherever Roger has 0, and 0 wherever Roger has 1. Since a Turing machine suffices for converting Roger into Roller, or Roller into Roger, Roller and Roger might be called "T-similar infinite random sequences".

An equally Turing-feasible, although less compactly Turing-feasible, variant on Roger is Roper. Roper agrees with Roger in his jth position, for every j which is not prime. At each of the P-positions, on the other hand (the 2nd position, the 3rd position, the 5th position, the 7th position, the 11th position, ...) Roper has 1 if Roger has 0, and has 0 if Roger has 1. Again, Roger and Roper might be called "T-similar infinite random sequences".

Further, since the internal program tables for the two Turing machines just envisaged can be amalgamated into the internal program table for a single, more intricate, Turing machine, Roller and Roper themselves prove to be "T-Similar infinite random sequences".

What order-of-infinity questions now arise in the topic of T-Similar Random Infinite Bit Sequences - and, for that matter, in the separate-but-parallel topic of IT-Similar Random Infinite Bit Sequences?

In working on this, it is conceivably helpful to recall two basic observations from previous weeks:

  • The set of all Turing machines is of the same order of infinity as the set of positive integers. 
  • The set of all infinite bit sequences is of a higher order of infinity than the set of positive integers. 
[This is the end of the current blog posting.]









No comments:

Post a Comment

All comments are moderated. For comment-moderation rules, see initial posting on this blog (2016-04-14).