The First Trichotomy. Thought of the Day 119.0

sign_aspects

As the sign consists of three components it comes hardly as a surprise that it may be analyzed in nine aspects – every one of the sign’s three components may be viewed under each of the three fundamental phenomenological categories. The least discussed of these so-called trichotomies is probably the first, concerning which property in the sign it is that functions, in fact, to make it a sign. It gives rise to the trichotomy qualisign, sinsign, legisign, or, in a little more sexy terminology, tone, token, type.

The oftenmost quoted definition is from ‘Syllabus’ (Charles S. Peirce, The Essential Peirce Selected Philosophical Writings, Volume 2):

According to the first division, a Sign may be termed a Qualisign, a Sinsign, or a Legisign.

A Qualisign is a quality which is a Sign. It cannot actually act as a sign until it is embodied; but the embodiment has nothing to do with its character as a sign.

A Sinsign (where the syllable sin is taken as meaning ‘being only once’, as in single, simple, Latin semel, etc.) is an actual existent thing or event which is a sign. It can only be so through its qualities; so that it involves a qualisign, or rather, several qualisigns. But these qualisigns are of a peculiar kind and only form a sign through being actually embodied.

A Legisign is a law that is a Sign. This law is usually [sic] established by men. Every conventional sign is a legisign. It is not a single object, but a general type which, it has been agreed, shall be significant. Every legisign signifies through an instance of its application, which may be termed a Replica of it. Thus, the word ‘the’ will usually occur from fifteen to twenty-five times on a page. It is in all these occurrences one and the same word, the same legisign. Each single instance of it is a Replica. The Replica is a Sinsign. Thus, every Legisign requires Sinsigns. But these are not ordinary Sinsigns, such as are peculiar occurrences that are regarded as significant. Nor would the Replica be significant if it were not for the law which renders it so.

In some sense, it is a strange fact that this first and basic trichotomy has not been widely discussed in relation to the continuity concept in Peirce, because it is crucial. It is evident from the second noticeable locus where this trichotomy is discussed, the letters to Lady Welby – here Peirce continues (after an introduction which brings less news):

The difference between a legisign and a qualisign, neither of which is an individual thing, is that a legisign has a definite identity, though usually admitting a great variety of appearances. Thus, &, and, and the sound are all one word. The qualisign, on the other hand, has no identity. It is the mere quality of an appearance and is not exactly the same throughout a second. Instead of identity, it has great similarity, and cannot differ much without being called quite another qualisign.

The legisign or type is distinguished as being general which is, in turn, defined by continuity: the type has a ‘great variety of appearances’; as a matter of fact, a continuous variation of appearances. In many cases even several continua of appearances (as &, and, and the spoken sound of ‘and’). Each continuity of appearances is gathered into one identity thanks to the type, making possible the repetition of identical signs. Reference is not yet discussed (it concerns the sign’s relation to its object), nor is meaning (referring to its relation to its interpretant) – what is at stake is merely the possibility for a type to incarnate a continuum of possible actualizations, however this be possible, and so repeatedly appear as one and the same sign despite other differences. Thus the reality of the type is the very foundation for Peirce’s ‘extreme realism’, and this for two reasons. First, seen from the side of the sign, the type provides the possibility of stable, repeatable signs: the type may – opposed to qualisigns and those sinsigns not being replicas of a type – be repeated as a self-identical occurrence, and this is what in the first place provides the stability which renders repeated sign use possible. Second, seen from the side of reality: because types, legisigns, are realized without reference to human subjectivity, the existence of types is the condition of possibility for a sign, in turn, to stably refer to stably occurring entities and objects. Here, the importance of the irreducible continuity in philosophy of mathematics appears for semiotics: it is that which grants the possibility of collecting a continuum in one identity, the special characteristic of the type concept. The opposition to the type is the qualisign or tone lacking the stability of the type – they are not self-identical even through a second, as Peirce says – they have, of course, the character of being infinitesimal entities, about which the principle of contradiction does not hold. The transformation from tone to type is thus the transformation from unstable pre-logic to stable logic – it covers, to phrase it in a Husserlian way, the phenomenology of logic. The legisign thus exerts its law over specific qualisigns and sinsigns – like in all Peirce’s trichotomies the higher sign types contain and govern specific instances of the lower types. The legisign is incarnated in singular, actual sinsigns representing the type – they are tokens of the type – and what they have in common are certain sets of qualities or qualisigns – tones – selected from continua delimited by the legisign. The amount of possible sinsigns, tokens, are summed up by a type, a stable and self-identical sign. Peirce’s despised nominalists would to some degree agree here: the universal as a type is indeed a ‘mere word’ – but the strong counterargument which Peirce’s position makes possible says that if ‘mere words’ may possess universality, then the world must contain it as well, because words are worldly phenomena like everything else. Here, nominalists will typically exclude words from the world and make them privileges of the subject, but for Peirce’s welding of idealism and naturalism nothing can be truly separated from the world – all what basically is in the mind must also exist in the world. Thus the synthetical continuum, which may, in some respects, be treated as one entity, becomes the very condition of possibility for the existence of types.

Whether some types or legisigns now refer to existing general objects or not is not a matter for the first trichotomy to decide; legisigns may be part of any number of false or nonsensical propositions, and not all legisigns are symbols, just like arguments, in turn, are only a subset of symbols – but all of them are legisigns because they must in themselves be general in order to provide the condition of possibility of identical repetition, of reference to general objects and of signifying general interpretants.

Universal Turing Machine: Algorithmic Halting

169d342be4ac9fdca10d1c8c9c04c3df

A natural number x will be identified with the x’th binary string in lexicographic order (Λ,0,1,00,01,10,11,000…), and a set X of natural numbers will be identified with its characteristic sequence, and with the real number between 0 and 1 having that sequence as its dyadic expansion. The length of a string x will be denoted |x|, the n’th bit of an infinite sequence X will be noted X(n), and the initial n bits of X will be denoted Xn. Concatenation of strings p and q will be denoted pq.

We now define the information content (and later the depth) of finite strings using a universal Turing machine U. A universal Turing machine may be viewed as a partial recursive function of two arguments. It is universal in the sense that by varying one argument (“program”) any partial recursive function of the other argument (“data”) can be obtained. In the usual machine formats, program, data and output are all finite strings, or, equivalently, natural numbers. However, it is not possible to take a uniformly weighted average over a countably infinite set. Chaitin’s universal machine has two tapes: a read-only one-way tape containing the infinite program; and an ordinary two-way read/write tape, which is used for data input, intermediate work, and output, all of which are finite strings. Our machine differs from Chaitin’s in having some additional auxiliary storage (e.g. another read/write tape) which is needed only to improve the time efficiency of simulations.

We consider only terminating computations, during which, of course, only a finite portion of the program tape can be read. Therefore, the machine’s behavior can still be described by a partial recursive function of two string arguments U(p, w), if we use the first argument to represent that portion of the program that is actually read in the course of a particular computation. The expression U (p, w) = x will be used to indicate that the U machine, started with any infinite sequence beginning with p on its program tape and the finite string w on its data tape, performs a halting computation which reads exactly the initial portion p of the program, and leaves output data x on the data tape at the end of the computation. In all other cases (reading less than p, more than p, or failing to halt), the function U(p, w) is undefined. Wherever U(p, w) is defined, we say that p is a self-delimiting program to compute x from w, and we use T(p, w) to represent the time (machine cycles) of the computation. Often we will consider computations without input data; in that case we abbreviate U(p, Λ) and T(p, Λ) as U(p) and T(p) respectively.

The self-delimiting convention for the program tape forces the domain of U and T, for each data input w, to be a prefix set, that is, a set of strings no member of which is the extension of any other member. Any prefix set S obeys the Kraft inequality

p∈S 2−|p| ≤ 1

Besides being self-delimiting with regard to its program tape, the U machine must be efficiently universal in the sense of being able to simulate any other machine of its kind (Turing machines with self-delimiting program tape) with at most an additive constant constant increase in program size and a linear increase in execution time.

Without loss of generality we assume that there exists for the U machine a constant prefix r which has the effect of stacking an instruction to restart the computation when it would otherwise end. This gives the machine the ability to concatenate programs to run consecutively: if U(p, w) = x and U(q, x) = y, then U(rpq, w) = y. Moreover, this concatenation should be efficient in the sense that T (rpq, w) should exceed T (p, w) + T (q, x) by at most O(1). This efficiency of running concatenated programs can be realized with the help of the auxiliary storage to stack the restart instructions.

Sometimes we will generalize U to have access to an “oracle” A, i.e. an infinite look-up table which the machine can consult in the course of its computation. The oracle may be thought of as an arbitrary 0/1-valued function A(x) which the machine can cause to be evaluated by writing the argument x on a special tape and entering a special state of the finite control unit. In the next machine cycle the oracle responds by sending back the value A(x). The time required to evaluate the function is thus linear in the length of its argument. In particular we consider the case in which the information in the oracle is random, each location of the look-up table having been filled by an independent coin toss. Such a random oracle is a function whose values are reproducible, but otherwise unpredictable and uncorrelated.

Let {φAi (p, w): i = 0,1,2…} be an acceptable Gödel numbering of A-partial recursive functions of two arguments and {φAi (p, w)} an associated Blum complexity measure, henceforth referred to as time. An index j is called self-delimiting iff, for all oracles A and all values w of the second argument, the set { x : φAj (x, w) is defined} is a prefix set. A self-delimiting index has efficient concatenation if there exists a string r such that for all oracles A and all strings w, x, y, p, and q,if φAj (p, w) = x and φAj (q, x) = y, then φAj(rpq, w) = y and φAj (rpq, w) = φAj (p, w) + φAj (q, x) + O(1). A self-delimiting index u with efficient concatenation is called efficiently universal iff, for every self-delimiting index j with efficient concatenation, there exists a simulation program s and a linear polynomial L such that for all oracles A and all strings p and w, and

φAu(sp, w) = φAj (p, w)

and

ΦAu(sp, w) ≤ L(ΦAj (p, w))

The functions UA(p,w) and TA(p,w) are defined respectively as φAu(p, w) and ΦAu(p, w), where u is an efficiently universal index.

For any string x, the minimal program, denoted x∗, is min{p : U(p) = x}, the least self-delimiting program to compute x. For any two strings x and w, the minimal program of x relative to w, denoted (x/w)∗, is defined similarly as min{p : U(p,w) = x}.

By contrast to its minimal program, any string x also has a print program, of length |x| + O(log|x|), which simply transcribes the string x from a verbatim description of x contained within the program. The print program is logarithmically longer than x because, being self-delimiting, it must indicate the length as well as the contents of x. Because it makes no effort to exploit redundancies to achieve efficient coding, the print program can be made to run quickly (e.g. linear time in |x|, in the present formalism). Extra information w may help, but cannot significantly hinder, the computation of x, since a finite subprogram would suffice to tell U to simply erase w before proceeding. Therefore, a relative minimal program (x/w)∗ may be much shorter than the corresponding absolute minimal program x∗, but can only be longer by O(1), independent of x and w.

A string is compressible by s bits if its minimal program is shorter by at least s bits than the string itself, i.e. if |x∗| ≤ |x| − s. Similarly, a string x is said to be compressible by s bits relative to a string w if |(x/w)∗| ≤ |x| − s. Regardless of how compressible a string x may be, its minimal program x∗ is compressible by at most an additive constant depending on the universal computer but independent of x. [If (x∗)∗ were much smaller than x∗, then the role of x∗ as minimal program for x would be undercut by a program of the form “execute the result of executing (x∗)∗.”] Similarly, a relative minimal program (x/w)∗ is compressible relative to w by at most a constant number of bits independent of x or w.

The algorithmic probability of a string x, denoted P(x), is defined as {∑2−|p| : U(p) = x}. This is the probability that the U machine, with a random program chosen by coin tossing and an initially blank data tape, will halt with output x. The time-bounded algorithmic probability, Pt(x), is defined similarly, except that the sum is taken only over programs which halt within time t. We use P(x/w) and Pt(x/w) to denote the analogous algorithmic probabilities of one string x relative to another w, i.e. for computations that begin with w on the data tape and halt with x on the data tape.

The algorithmic entropy H(x) is defined as the least integer greater than −log2P(x), and the conditional entropy H(x/w) is defined similarly as the least integer greater than − log2P(x/w). Among the most important properties of the algorithmic entropy is its equality, to within O(1), with the size of the minimal program:

∃c∀x∀wH(x/w) ≤ |(x/w)∗| ≤ H(x/w) + c

The first part of the relation, viz. that algorithmic entropy should be no greater than minimal program size, is obvious, because of the minimal program’s own contribution to the algorithmic probability. The second half of the relation is less obvious. The approximate equality of algorithmic entropy and minimal program size means that there are few near-minimal programs for any given input/output pair (x/w), and that every string gets an O(1) fraction of its algorithmic probability from its minimal program.

Finite strings, such as minimal programs, which are incompressible or nearly so are called algorithmically random. The definition of randomness for finite strings is necessarily a little vague because of the ±O(1) machine-dependence of H(x) and, in the case of strings other than self-delimiting programs, because of the question of how to count the information encoded in the string’s length, as opposed to its bit sequence. Roughly speaking, an n-bit self-delimiting program is considered random (and therefore not ad-hoc as a hypothesis) iff its information content is about n bits, i.e. iff it is incompressible; while an externally delimited n-bit string is considered random iff its information content is about n + H(n) bits, enough to specify both its length and its contents.

For infinite binary sequences (which may be viewed also as real numbers in the unit interval, or as characteristic sequences of sets of natural numbers) randomness can be defined sharply: a sequence X is incompressible, or algorithmically random, if there is an O(1) bound to the compressibility of its initial segments Xn. Intuitively, an infinite sequence is random if it is typical in every way of sequences that might be produced by tossing a fair coin; in other words, if it belongs to no informally definable set of measure zero. Algorithmically random sequences constitute a larger class, including sequences such as Ω which can be specified by ineffective definitions.

The busy beaver function B(n) is the greatest number computable by a self-delimiting program of n bits or fewer. The halting set K is {x : φx(x) converges}. This is the standard representation of the halting problem.

The self-delimiting halting set K0 is the (prefix) set of all self-delimiting programs for the U machine that halt: {p : U(p) converges}.

K and K0 are readily computed from one another (e.g. by regarding the self-delimiting programs as a subset of ordinary programs, the first 2n bits of K0 can be recovered from the first 2n+O(1) bits of K; by encoding each n-bit ordinary program as a self-delimiting program of length n + O(log n), the first 2n bits of K can be recovered from the first 2n+O(log n) bits of K0.)

The halting probability Ω is defined as {2−|p| : U(p) converges}, the probability that the U machine would halt on an infinite input supplied by coin tossing. Ω is thus a real number between 0 and 1.

The first 2n bits of K0 can be computed from the first n bits of Ω, by enumerating halting programs until enough have halted to account for all but 2−n of the total halting probability. The time required for this decoding (between B(n − O(1)) and B(n + H(n) + O(1)) grows faster than any computable function of n. Although K0 is only slowly computable from Ω, the first n bits of Ω can be rapidly computed from the first 2n+H(n)+O(1) bits of K0, by asking about the halting of programs of the form “enumerate halting programs until (if ever) their cumulative weight exceeds q, then halt”, where q is an n-bit rational number…

Wittgenstein’s Form is the Possibility of Structure

nb6

For given two arbitrary objects x and y they can be understood as arguments for a basic ontological connection which, in turn, is either positive or negative. A priori there exist just four cases: the case of positive connection – MP, the case of negative connection – MI, the case that connection is both positive and negative, hence incoherent, denoted – MPI, and the most popular in combinatorial ontology the case of mutual neutrality – N( , ). The first case is taken here to be fundamental.

Explication for σ

Now we can offer the following, rather natural explication for a powerful, nearly omnipotent, synthesizer: y is synthetizable from x iff it is be made possible from x:

σ(x) = {y : MP(x,y)}

Notice that the above explication connects the second approach (operator one) with the third (internal) approach to a general theory of analysis and synthesis.

Quoting one of the most mysterious theses of Wittgenstein’s Tractatus:

(2.033) Form is the possibility of structure.

Ask now what the possibility means? It has been pointed out by Frank Ramsey in his famous review of the Tractatus that it cannot be read as a logical modality (i. e., form cannot be treated as an alternative structure), for this reading would immediately make Tractatus inconsistent.

But, rather ‘Form of x is what makes the structure of y possible’.

Formalization: MP(Form(x), Str(y)), hence – through suitable generalization – MP(x, y).

Wittgensteinian and Leibnizian clues make the nature of MP more clear: form of x is determined by its substance, whereas structurality of y means that y is a complex built up in such and such way. Using syntactical categorization of Lésniewski and Ajdukiewicz we obtain therefore that MP has the category of quantifier: s/n, s – which, as is easy to see, is of higher order and deeply modal.

Therefore M P is a modal quantifier, characterized after Wittgenstein’s clue by

MP(x, y) ↔ MP(S(x), y)