Monday 20 November 2017

Toomas Karmo: Part R: 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.


  • 20171123T0418Z/4.4.0: Kmo expanded the homework assignment. - He reserved the right to make further tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 4.4.1, 4.4.2, 4.4.3, ... . 
  • 20171122T2125Z/4.3.0: Kmo made a couple of further improvements of substance: (1) he tightened up his exposition of the Halting Problem, filling in a potentially troubling detail, regarding starting the machines on an initially all-blanks string,  which he had failed to spell out properly; (2) he took more care with von Mises and Martin-Löf-with-Levin-with-Schnorr, now only saying that these writers can be the BASIS for suggesting a candidate nontrivially necessary condition for "infinite bit string S is random". (HIs previous wording perhaps read too much into these writers, by saying that they had THEMSELVES asserted some candidate nontrivially necessary condition for "infinite bit string S is random".) - Kmo reserved the right to make further tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 4.3.1, 4.3.2, 4.3.3, .. . 
  • 20171122T2008Z/4.2.0: Kmo made some improvements of substance: he cited one particular Web exposition of Turing machines; he tightened up, or at least made a little more vivid, his discussion of Turing machines and blank squares; he outlined a way of mapping the Turing machines 1-to-1 onto the natural numbers; and he noted that, even apart from the historical Prof. A. Turing's own Halting-Problem argument, elementary Cantor considerations of cardinality demonstrate the existence of Turing-noncomputable infinite bit sequences. - He reserved the right to make further tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 4.2.1, 4.2.2, 4.2.3, .. . 
  • 20171121T1753Z/4.1.0: Kmo found it to his chagrin necessary to correct some small, but neverhtless substantive, technical errors (including, at one point, a mischaracterization of a 1-to-1 "into" mapping). - He reserved the right to make further tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 4.1.1, 4.1.2, 4.1.3, .. . 
  • 20171121T1407Z/4.0.0: Kmo finished converting his point-form outline into coherent full-sentences prose. - He reserved the right to make further tiny, nonsubstantive, purely cosmetic, tweaks over the coming 48 hours, as here-undocumented versions 4.0.1, 4.0.2, 4.0.3, .. . 
  • 20171121T0444Z/3.0.1: Kmo made some minuscule cosmetic tweaks (correcting such things as typos), before finally deciding he had to get to bed.
  • 20171121T0432Z/version 3.0.0: Kmo managed to upload a reasonably polished fine-grained outline, scaling back a little on the writing plan he had put into version 2.0.0. (That writing plan was a bit too much for one week's work, containing as it did his detailed verdicts on (a) von Mises and  (b) Martin-Löf with Schnorr with Levin. He now decided that the detailed verdicts would have to wait until at least his next installment. - Kmo found it now advisable to end for the night, deferring the construction of fully satisfactory prose from this detailed outline to the following morning. He hoped to have the fully-satisfactory-prose version finished by UTC=20171121T1900Z.
  • 20171121T0056Z/version 2.0.0: Kmo repaired his "version 1.0.0" upload, which had been accidentally truncated.
  • 20171121T0001Z/version 1.0.0: Kmo had time to upload a coarse-grained outline. He hoped over the coming 4 or 5 hours first to convert this into a fine-grained outline, and then to convert the fine-grained 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.]


Since the upload of 2017-05-15 or 2017-05-16, I have been composing, off and on, with sporadic uploads, a multi-part essay on the philosophy of perception, of action, and of what I propose to be calling (eventually) "Subjectivity". This present installment comes a little later than I had hoped. The delay was caused by my having for part of this month to attend not to philosophy but to the practical blogspot-cum-blogger implications of Ontario's David Dunlap Observatory and Park heritage-conservation file. 

****

The first two elements, perception and action, in this sequence of three have now perhaps been explored as thoroughly as they can be without my embarking on the specially troubling, and in my slow writing so far largely impending, concept of "Subjectivity". In my previous installment, "Part Q" (on 2017-10-30 or 2017-10-31), I did write a little on "Subjectivity", but only in a spirit of prudent management. It was necessary for me to ensure that my ideas would be on the Web in at least some schematic form, in case I suffered - this seemed, to be sure, only a remote, abstract, contingency - some misfortune prematurely terminating my Web publishing. Now, contentedly enough finding myself continuing to blog, I pick up where I left off in Parts O and P (from 2017-10-02/2017-10-03 and 2017-10-23/2017-10-24, respectively). 

In Parts O and P, I was mainly tidying up loose ends. Having already written at length on perception and action, I felt by the time Parts O and P came round that it would be advisable to fill out my emerging "Geography of the Mind", adding appropriate contextual comments on imagining and thinking. 

Admittedly, even a treatment of all four of perceiving, acting, imagining, and thinking, with also appropriately detailed supplements (lacking so far) on "Subjectivity", would fall short of a full Geography of the Mind. The list I have just given leaves out three topics relevant to the ethics-engaged mind, namely Emoting, Desiring, and Evaluating.  

I use "Emoting" as a generic term for feeling amused, feeling pleased, feeling fearful, and the like.

Desiring, or wanting, is already in some ways perhaps more subtle than emoting. Following Prof. Elizabeth Anscombe, we might note the special logical absurdity of some crowd's chanting "What do we want? A Saucer of Mud! When do we want it? NOW!" - given, at least, that the crowd is unable to give an answer to the question, "Well, why do you want a saucer of mud; what benefit to you do you perceive in acquiring such a prima facie pointless thing?" - Admittedly (Prof. Anscombe herself makes this clear), the feeling of logical absurdity would be alleviated if the crowd returned even some simple, childlike, answer to the People in Charge, for instance "Well, we crave just one benefit - a benefit so tiny, so humble, and for Your Lordship or Your Worship so easily bestowed: we desire just one thing we can possess. Our modest ambition is to have just one thing To Call Our Very Own." I suppose the crowd could then continue by citing the commendation of private ownership constructed by Leo XIII in the 1891 Papal encyclical Rerum novarum. - To Prof. Anscombe's discussion, we might add there is also such a well-known clinical phenomenon as lusting sexually after particular objects (footwear and lingerie are prominent in clinical discussions), and that someone might therefore answer the question by saying "Well, we have a Saucer of Mud fetish." Such an answer would once again alleviate the feeling of logical absurdity. Here, however, we have "desire" only in a very rudimentary sense, in which the rather elevated terrain of wanting slopes downward into the simpler, so-to-speak more animal, terrain of mere emoting. (As with the sexual appetite, so too with, for example, the appetite for food. There are clinical pathologies in which the subject has a craving to eat something known to the subject to lack nutrients, such as rock, sponge, or soil. - Fetishistic lusting and craving-as-for-food resemble, again, the simple, so-to-speak primitively animalian, phenomenon of fearing. A person might have an "irrational phobia" of Saucers of Mud. "Linophobia" is already a recognized term for fear of string. The corresponding term for fear for mud would be, perhaps, pelophobia or borborophobia. And on the other hand, the Anscombean sense in which a saucer of mud cannot coherently be wanted "just like that" has a parallel with the not-primitively-animalian attitudes of admiring and loving. A mob professing to admire, or again to love, a saucer of mud will be considered incoherent unless it can answer the question, "Well, what about that object is admirable?" or, again,  "What particular thing, what particular collocation of attributes or to-you-notable historical associations, is it you love in that object?" (A kinda-sorta coherent answer to either question might start, "Oh, we consider every saucer of mud to be an incarnation of the Great God Ukku-Phlup'pu,..."))

"Evaluating" is here my term for what we do when we say "I consider-to-be-valuable," "I approve," "I judge to be good." As desiring and emoting are connected and yet distinct, so also are desiring and evaluating connected and yet distinct. They are distinct in that, for example, one can find oneself saying, perhaps in self-accusatory chagrin, "I want a thing which I judge to be [in at any rate some sense] not good."

Philosophical essays, however prolix, do have to stop somewhere. It is natural enough to set a boundary here, by limiting the Geography of Mind to topics outside the special domain of ethics, and thereby to leave out desiring, emoting, and evaluating. 

Part O is now perhaps a sufficient exploration of the not-too-scary topic of imagining. The topic of thinking, on the other hand, is more difficult. I did not come close to exhausting it in Parts O and P. Toward the end of Part O, I did say something to bring out the special status of thinking (examining, for instance, the notion of perceptual, agentual, and imaginational "supports" for thinking, and asking as homework for Part P, what further things can now be said about thinking, over and above what I have said already, to differentiate it still further from perceiving, from acting, from the imagining of perceiving, and from the imagining of acting?).

In Part P, I gave a partial answer. In my partial answer, I got as far as distinguishing thoughtfully being (this might also, I said back then, be called "thinking in being") from thinking about being. I finished Part P with homework as I finished part O, this time inviting the reader to investigate further the notion of thinking about being. The homework asked the reader to look at this in the specific connection of mathematical randomness. That concept (I noted, or at any rate hinted, at the end of Part P) proves troubling. Investigating what it is to think-about-randomness, I felt back then (and still this week feel), would help to bring out the sense in which thinking-about-being is deep.

Indeed, I would this week go so far as to suggest that thinking-about-being is a distinctively deep thing in the entire Geography of Mind. My suspicion is that thinking-about-being is the really scary achievement, so to speak two or three orders of magnitude more problematic than the primitively animalian performances of perceiving, acting, imagining-perceiving, and imagining-acting (perhaps fish and reptiles get that far?), and even one or two orders of magnitude more problematic than those topics of some special concern in Part P, thoughtfully perceiving and thoughtfully acting. (That pair of topics falls perhaps within the province of at least the more accomplished of the non-human mammals. The temperamental Siamese cat warily contemplating the stranger, while hissing, might well be not just perceiving (and of course emoting), but even thoughtfully, in other words mindfully, perceiving.)

With thinking-about-being - involving as it typically does, at least in the earthly modes of living with which we are familiar, "supports", in the form of symbols seen-or-heard, symbols imagined-as-seen-or-heard, symbols written-or-uttered, or symbols imagined-as-being-written-or-uttered - we perhaps reach a field inaccessible to the quadrupeds, and attained within the lives of our own biosphere only by Homo sapiens and a select few other mammals. One does perhaps like to speculate that the whales, when performing their intricate subsea songs, are producing symbolic supports for thinking-about-being. But maybe they are, on the other hand, just having unthinking fun, like temporarily beer-sozzled engineering undergrads who, having temporarily deserted their so-necessary calculus desks, are momentarily generating rap music?

****


In what follows, we consider for the most part just the notion of a random or a nonrandom infinite bit sequence, in the style 01000100111011... Such a sequence has a first term, a second term, and so on, with each term being either an "OF" (a 0), or an "ON" (a 1). This is the same conception of infinite sequence as I used in Part O (on 2017-10-02 or 2017-10-03), when recapitulating the Georg Cantor proof that the collection of all infinite bit sequences is of a higher order of infinity than the mere collection of natural numbers 1, 2, 3, .. . (It might perhaps be worth adding this week that the collection of finite bit sequences is, by contrast, of the same low, humble, order of infinity as the collection of natural numbers. It is easy enough to associate with every finite bit sequence some natural number or other, in such a way that no two distinct finite bit sequences get paired with the same number (marriages are, to speak, constrained to monogamy), and in such a way that every natural number gets associated with some bit sequence or other (not only bachelorhood, so to speak, but even spinsterhood, is forbidden). In other words, the universe of finite bit sequences is only infinite in the naive, humble, sense in which the natural numbers themselves are infinite, through a proof which exhibits that universe as "mappable one-to-one onto the natural numbers".) 

I now turn to another preliminary remark, intended to secure a possible (mild) convenience in exposition. I introduce now the term "orderly", as shorthand for "not random". On my adopted terminology, every infinite bit sequence is either random or orderly, and no infinite bit sequence is both random and orderly. 

In introducing the terminology, I do not herewith claim that the two disjoint, mutually exclusive, sets, "the set of random infinite bit sequences" and "the set of orderly infinite bit sequences", both succeed in being nonempty. As I hope we shall be seeing in a subsequent installment, the very question "ARE there any truly random infinite bit sequences?" harbours its depths, in other words houses its potential seeds of controversy. 

It will in some subsequent week be appropriate to examine also questions of degree. I hope in due course to be explaining how a random infinite bit sequence (assuming such a thing to exist at all) might be "very random" or "just mildly random", and how an orderly infinite bit sequence might be "very orderly" or "just mildly orderly". 

In what follows, I will additionally assume that the reader either already has, or else can now acquire by Googling, the usual notion of a Turing machine. I will herewith take as my official definition the definition from https://en.wikipedia.org/wiki/Turing_machine, in the section headed "Formal definition". In fact, however, any mainstream Google-retrievable discussion is pretty well bound to agree with my official definition in all but inconsequential details.

I now recapitulate some key points from Wikipedia, with a couple of additions. (1) For maximum clarity, I add a particular alphabet specification, plus a notion of "Boot Square". (2) I introduce the (surely, give or take a few inconsequential details, usual) notion of a non-halting Turing machine's "generating" a particular infinite sequence of bits:

  • A Turing machine works from a program table of finite length. 
  • A Turing machine works with an infinite tape, not necessarily initially blank, having no first square and having no last square, where one of these squares is to be thought of as the square (the "Boot-Time Square") under the read-write head at the instant the machine starts up, in duly starting from the top of its program table. 
  • A Turing machine reads and writes a finite, twenty-nine-character alphabet, namely a blank, or "whitespace", and the twenty-six letters a, b, c, ... z, and the two numerals 0 and 1
  • The only character which is allowed to be present in infinitely many occurrences at any stage in a Turing-machine computation is the blank. (So, in particular, if the tape at start time is not entirely blank, it has only finitely many non-blank squares.)
  • Although a Turing machine has, as already stated, a program table of finite length, it might (1) cause, when run with an initially all-blanks tape, the tape eventually to harbour, forever onward from some instant, just some finite number of non-blank squares (from the instant of halting, in the special case where the machine eventually halts; but there are also other possibilities, for example the possibility that the machine runs on forever, while eventually ceasing to write anything), and alternatively (2) might (through running on forever) cause an initially all-blanks tape to harbour infinitely many written squares.
  • A Turing machine shall be said to "generate as its numerical output the infinite sequence 101110011..." (and the like) if and only if it never writes any numeral to the left of its Boot Square, and never overwrites a 0 once written, and never overwrites a 1 once written, and (while perhaps writing many a letter or blank on, or left of, or to the right of, the Boot Square, and perhaps even doing much overwriting of letters and blanks) is found to create on  its tape some sequence of letters and numerals and blanks whose purely numerical part is 101110011... (as it might be, ...pqrstu1ifsacv01bcv~na1gfg1f0fg0s~~j___w11t~uy... - with, as it might be, the just-displayed r sitting in its Boot Square; here I use "~" to represent the blank). .    
****

Trivially, every finite bit sequence is the numerical output from some eventually-halting Turing machine, when the machine is started on an all-blanks tape. Consider, e.g, the finite bit sequence 11101101. This is the numerical output of a Turing machine with a very dull program table.This dull table does not even mention the whitespace or any of the 26 available letters, but merely directs the machine to write the numeral 1 into its Boot Square (therein in fact, although the program is silent on this detail, overwriting the existing whitespace), then to move one square to the right and write 1 (therein overwriting the existing whitespace), then to move one square to the right and write 1 (therein overwriting the existing whitespace), then to move one square to the right and write 0 (therein overwriting the existing whitespace), then to move one square to the right and write 1 (therein overwriting the existing whitespace), then to move one square to the right and write 1 (therein overwriting the existing whitespace), then to move one square to the right and write 0 (therein overwriting the existing whitespace), then to move one square to the right and write 1 (therein overwriting the existing whitespace), and then halt.

Let an infinite bit sequence be termed "Turing-orderly" if and only if some never-halting Turing machine generates it as its numerical output.

A question now arises, exploring the so-problematic (and so relevant to the topic of thinking about being) concepts of orderliness and randomness: Is it (A) reasonable to say that the orderly infinite bit sequences are just the Turing-orderly infinite bit sequences, or is (B) the concept of an orderly infinite bit sequence (whatever exactly, I stress, this problematic concept might be) such that some orderly infinite bit sequences are not Turing-orderly? (Or, to put this in terms of randomness: (A) Is it an adequate characterization of randomness to say that the random infinite bit sequences are simply the infinite bit sequences which escape being generated by any of the (individually finite) members in the (collectively infinite) ensemble of possible Turing machines? Or (B) are there some "specially problematic" infinite bit sequences which are "in just a subtle sense orderly", being generated by no one Turing machine in the infinite ensemble, and yet in some subtle way falling short of true randomness?) The subtlety of the concept of randomness, and with it (eventually, as I hope) the depth of the concept of thinking-about-being, emerges when we realize that it is "(B)", not "(A)", that has to be the right answer. 

It is a known result, from the work of the actual historical Prof. A. Turing (1912-1954), that no Turing machine can solve the "Halting Problem". For present purposes, the exposition of Prof. A. Turing's result should begin as follows: Take any encoding scheme which associates with every Turing machine some natural number, and never associates the same natural number with two different Turing machines, and associates every natural number with some Turing machine or other.

The existence of such encoding schemes is guaranteed by the fact that every Turing machine has just a finite program table, and that there is just a finite alphabet - here comprising, in fact, just the whitespace character, the letters a, b, ... , z, and the two numerals 0 and 1 - with which each member in the entire (collectively infinite)  ensemble of (individually finite) Turing machines is allowed to work.

For concreteness, I will outline the particular encoding scheme I have in mind. Let each Turing machine in our ensemble be represented by a finite sequence of 5-tuples, in the spirit of the Turing-Davis formalization described in the here-cited section of the here-cited Wikipedia article. Take some convenient finite alphabet A, having two or more characters, and with some particular ordering prescribed for the characters. (The Roman a-in-order-out-to-z alphabet fits this specification. So does the Hebrew-consonantal-without-pointing aleph-in-the-usual-prescribed-order-out-to-taw alphabet. So, as a third example, does the Cyrillic "а"-in-the-usual-prescribed-order-out-to-"я" alphabet.) Call an "A-word" a finite nonempty string of A-characters. (So if, e.g., the Cyrillic alphabet is selected for A, three sample A-words are яшз, я, and  яяшзцццуосагяяшзцосццг.) Work out some way of encoding each such finite sequence of 5-tuples as an A-word. (So if, say, the simple Turing machine T has a Turing-Davis representation as a sequence of just three 5-tuples, and the more intricate Turing machine U has a Turing-Davis representation as a sequence of three million 5-tuples, T is encoded as a single, rather short, A-word, and U is encoded as a single, dauntingly long, A-word.) Out of the entire ensemble of A-words, consider those A-words w to be "Turing-machine A-words" which are such that w encodes some Turing machine. Now, with reference to the prescribed ordering on A, arrange the Turing-machine A-words into an infinite sequence, in A-prescribed alphabetical order. Every Turing machine appears exactly once in the resulting list, or "dictionary listing of Turing-machine A-words". The list therefore generates a 1-to-1 mapping of the Turing machines (not merely into, but even onto) the natural numbers 1, 2, 3, ... - with the Turing machine dictionary-listed as kth corresponding to natural number k, for each k = 1, 2, 3, ... .

Some duly knowledgeable readers will notice that I have here dodged a possible, although I think an ultimately irrelevant, distraction: I have not only set up a 1-to-1 correspondence between the Turing machines and the natural numbers, but have ensured that my correspondence is itself "straightforwardly computable", i.e., "straightforwardly algorithmic".  (I will not here venture into the topic - I think it is an irrelevant distraction - of correspondences between Turing machines and natural numbers which are in some sense "NOT straightforwardly computable".)

From mere considerations of orders of infinity, as discussed with reference to Cantor in Part O (on 2017-10-02 or 2017-10-03), it already follows that infinite bit sequences exist which are not generated as the numerical output of any Turing machine.  This follows because the Turing machines can be mapped, as shown above, 1-to-1 onto the natural numbers, whereas the overall grand class of infinite bit sequences (as shown in Part O) cannot be.

The historical Prof. A. Turing, on the other hand, demonstrated the limitations of Turing machines in a more concrete fashion, by proving that no Turing machine T solves the "Halting Problem".

The following is what is herewith and henceforth (as I recapitulate Prof. Turing's result in my own words) deemed a solution to the "Halting Problem":  Given a tape blank except for a 1 in its Boot Square, and a 1 in the square immediately to the right of its Boot Square, and so on for some finite number of squares (given, let us herewith and henceforth say, a "Well-Formed Input String"), if the total number k of 1s in the input is the number dictionary-paired with some Turing machine that eventually halts when started with an initially-all-blank tape, T halts eventually, immediately after printing just to the left of its Boot Square the letter y (for "Yes, it eventually halts when started on an all-blanks tape"); and if k is the number dictionary-paired with some Turing machine that runs forever when started with an initially-all-blank tape, T again halts eventually, immediately after writing immediately to the left of its Boot Square the letter n (for "No, it does not halt when started on an initially-all-blanks tape"). (To make this definition of "solving the Halting Problem" specially user-friendly - to make it as-it-were a piece of specially simple choreography - let us add that if k is not dictionary-paired with any Turing machine, T likewise eventually halts, immediately after writing immediately to the left of its Boot Square the letter x. So on this user-friendly definition, the hypothetical T (proved, I stress, by Prof. Turing not to exist) always halts when given a "Well-Formed Input String".) 

I have not myself taken the trouble to review in recent years the proof that no Turing machine solves the "Halting Problem". But I do know, from my 1970s or 1980s studies (a) that the proof is not particularly long, and (b) that the proof uses an argument much in the spirit of the Cantor argument establishing that there is more than one "order of infinity" (the argument noted in Part O of this essay, from 2017-10-02 or 2017-10-03). It is gratifying that Prof. Turing's result both is deep and is amenable to a short proof  - in fact (if I may be a little vocal here) falling within the scope of some modest Department of Philosophy at some modest "Tallahassee Swampwater Junior Training College". Down at Swampwater, the profs would present it as, say, just one third of some undemanding single-semester course, though at slow-paced Swampwater perhaps in the third ("junior") B.A. programme year, as opposed to the first ("frosh") year or the second ("sophomore") year. 

Construct, now, what we might call the "Specially Troubling Orderly Sequence", or STOS. For each j = 1, 2, 3, ... , the STOS has in its jth position a 1 if j is a number dictionary-paired with a Turing machine that eventually halts when started on an all-blanks tape, and otherwise has a 0 in its jth position. 

On any adequate notion of "orderly", the STOS is an orderly, i..e. is a not-random, sequence. For look at it in terms of thinkers, deploying some degree of insight. (I borrow the portentous term "insight" from the Canadian Catholic philosopher (away with thee, Igominy and Humiligation Precept) Fr Bernard Lonergan (1904-1984), admittedly without having read him.) Even we limited human animals, with our small crania, can deploy enough insight into our thinking-about-being (deploying, perhaps, many a support for our thinking, with many an astute pencil notation on many a sheet of paper) to answer for many a Turing machine V the question, "Does V eventually halt when started on an all-blanks tape, or is V, on the contrary, doomed to run on forever when started on an all-blanks tape ?" If we can do this, exercising one or another hard-to-predict kind of mathematical creativity, for many a Turing machine V, we might well imagine the possibility of some thinker more powerful than a Homo sapiens achieving it for every Turing machine V. (Or, more carefully, we can imagine the possibility of some non-human thinker being so astute as to be able, for every Turing machine V, to achieve it for V in some finite stretch of time or other - perhaps, in some cases, a long stretch of time. The envisaged thinker might perhaps in some cases resort in the daunting creative-mathematics task to some finite number  - perhaps even a high number - of sheets of paper, and to some finite number - perhaps even a high number - of 0.5-millimetre hardness-grade-B mechanical-pencil graphites (with also those pretty-well-essential adjuncts to maths work, a set of erasable coloured pencils, and their accompanying sharpener).)

So, I stress, the STOS looks orderly. Nevertheless, if some Turing machine U were to generate the STOS as its numerical output, starting with a blank input tape, U could be upgraded, with some modest extension of its program table, into a Turing machine T that solves the (demonstrably insoluble) Halting Problem. We encounter, then, in the STOS a surprising thing - an infinite bit sequence orderly indeed, and yet orderly only in some subtle, not Turing-encapsulable, sense.

This application of the Turing Halting Problem work did rather surprise me when I noted it a couple of weeks ago, familiar though it must be to the appropriate Department of Mathematics professionals (that is, to the profs whose B.Sc.-level teaching duties embrace both what the campus calendar lists as "Mathematical Logic" and what the campus calendar lists as "Probability Theory").

It will be helpful for at least some readers if I make my point again, in different words.

Whatever it might mean for an infinite bit sequence to be orderly, there is at any rate a trivially and incontestably sufficient condition for orderliness (i.e., a trivially and incontestably necessary condition for randomness). Trivially and incontestably, it is sufficient for an infinite bit sequence to be orderly that some Turing machine generate it, from an initially blank input tape. (Equivalently: trivially and incontestably, it is necessary for an infinite bit sequence to be random that no Turing machine generate it from an initially blank input tape.) But now, surprisingly, it turns out that the condition incontestably sufficient for orderliness is not necessary (equivalently, that the condition incontestably necessary for randomness is not sufficient). Turing-noncomputability, in other words, surprisingly fails to guarantee randomness.

****

We want ultimately to produce a condition both necessary and sufficient for orderliness (equivalently, a condition both necessary and sufficient for randomness). One first, unavoidable, step in this quest for the definitional Holy Grail is the discovery of a condition which not only is sufficient for orderliness of an infinite bit sequence, but additionally is nontrivially sufficient (equivalently, is not only necessary for randomness, but is nontrivially necessary). In the next installment, I hope to violate, again, my increasingly threadbare Igominy and Humiligation Precept (from Part B, on 2017-05-22 or 2017-05-23), by examining two conceivable attempts to give a nontrivially sufficient condition for orderliness (equivalently, a nontrivially necessary condition for randomness). To nip in the bud any misleading impressions of erudition which I might be producing in readers, I stress at the outset that they are two attempts which I concoct in mere haste, from what very little I know of the relevant literature - in essence just from a hasty Wikipedia skim. Here bibliographical suggestions from readers, directed to Toomas.Karmo@gmail.com, would help me make my work more solid. 

One attempt, I think from before the war, is inspired by philosopher-physicist Ludwig von Mises (1881-1973). The other attempt is inspired by work of recent vintage, from the contemporary mathematical logicians Martin-Löf, Schnorr, and Levin. Those three mathematical logicians have in their turn been building upon finite-sequence ideas from Andrey Nikolaevich Kolmogorov (1903-1987). But for this week, I shall have to end.

As preparation for the next installment, interested readers might want to check in one of the rather obvious Wikipedia places for von Mises. For Martin-Löf et al, interested readers might want to concentrate on the passage in https://en.wikipedia.org/wiki/Algorithmically_random_sequence starting Leonid Levin and Claus-Peter Schnorr proved a characterization in terms of Kolmogorov complexity: a sequence is random if there is a uniform bound on the compressibility of its initial segments.

Having already confessed this week to a couple of kinds of shallowness, I have now additionally to confess to working on just one tiny bit of the article, essentially just the bit quoted here. 

So, Gentle Reader, here is some more homework: as we seek the Holy Grail of a necessary-and-sufficient condition, does at any rate a condition nontrivially sufficient for orderliness of an infinite bit sequence (equivalently, nontrivially necessary for randomness of an infinite bit sequence) emerge (a) from von Mises, and (b) from Martin-Löf with Levin and Schnorr? If that happy thing does not emerge, then does some other happy thing, like a condition necessary for orderliness of an infinite bit sequence (equivalently, a condition sufficient for randomness of an infinite bit sequence) at least emerge, from at least one of these two places in the literature? And if at any rate something useful, while falling short of the Holy Grail itself, emerges from at least one of these two places in the literature, can we then make a few remarks, of a modestly stocktaking character, on the extent to which our results are falling short?


[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).