Miser Project: Representing Functions in ‹ob›’s Abstract World

2019-11-12 Editing: Repair reflow where formulas are mangled.  Other touch-ups.
2019-11-05 Update: Complete separation from the WordPress version.
2019-11-03 Update: Touch-ups with initial migration to Blogger
2019-01-02 Update: Corrects ob.p01.bp representation of x ⊆ y and simplifies ob.p01.bp.is-eq(x,y) in boole.txt section 2.5.
2018-12-12 Update: The Boolean Algebra ob.bvx representations are adjusted to employ short-circuits and the ob.bvx.bvn interpretation improved.  Some things I just can’t let go by.
2018-12-10 Update: Representation of Boolean Algebra ob.bvx is simplified to make interpretation of ‹bvn› more direct and properly extensible.
2018-12-07 Update: Revamp the development of ob.bvx for interpretation of all Boolean Algebra structures via inter-interpretation, exposing more about the connection of mathematical structures and computational ones while also exposing the differences.

The structure ‹ob› = 〈Ob,Of,Ot〉is a mathematical, logical-theory conception that has  computational interpretation.  Software implementation for such an interpretation has been demonstrated.   So far, this is just for a depiction of some distinguished individuals (ob.NIL and lindies) and all the constructions possible over those.  The distinction of additional individuals is open-ended.

There are also canonical forms for all of the distinguished obs. This has obs be definite, however mathematically abstract.  It also has obs be finitely-expressible, even though there is no bound on the domain, Ob.

Representation of data, where obs are taken as encodings of data, thereby being interpretations of some other conception, has been suggested as a prospect for ‹ob›.  Now we turn to representation of functions and then representation of some structures other than ‹ob› .  The interpretations involved are mathematical in nature, not computational however suggestive they might be.

The separation (and useful connection) between mathematical characterizations and computational ones becomes more clear when we consider reasoning about functions and their representations in effectively-computable form, first the Of in ‹ob› and then representations and interpretations of other structures among each other and in ‹ob›. 

Preliminaries

1. Hark! Is That a Theory I See Before Me?
2. ‹ob› Primitive Functions
3. Narrowing ‹ob› for Computational Interpretation
4. Representing Data as Obs

1. The Abstraction of Functions

In structure ‹ob› = 〈Ob,Of,Ot〉, the characterization of functions in Of is by introduction of definitions using the theory language, Ot, just as there are mathematical expressions of the primitive notions.   Characterization in this manner demonstrates that the primitive functions and many other functions are in Of.

The way that a function f( x₁, x₂, .., x_n ) is successfully represented by an effectively-computable representation in Ot (or any other structure on the same principles as employed for ‹ob› here)  is with a small number of logical statements such that,

• there is a finite number of statements of finite length in the characterization.
• For definite operands, x₁, x₂, .., x_n, the definitions pertaining to
           f( x₁, x₂, .., x_n )
  lead to deduction, in a finite number of steps, to at most one definite result,
       y = f( x₁, x₂, .., x_n ).
• It can be the case that there is no definite result for some operands, x_i.
• When there is a definite result for all definite operands, x₁, x₂, .., x_n, f is said to be a total function.  It is defined on all obs.
• When there is no definite result for all definite operands,
  x₁, x₂, .., x_n, f is said to be a partial function that is undefined for those operands.
• It is not always possible to determine, from the offered characterization, whether a function is total or not.

Given two distinct representations in this manner, seemingly for function f and for function g,

• If f( x₁, x₂, .., x_n ) = g( x₁, x₂, .., x_n ) is deducible for all definite x, where each have definite result, we say that the same function is represented.
• We expect no counterpart of canonical forms for functions.  Determination that two representations are for the same function involves a mathematical proof.
• Determination that two representations are not for the same function is often by directly exhibiting operands x₁, x₂, .., x_n, for which
          f( x₁, x₂, .., x_n ) ≠ g( x₁, x₂, .., x_n )

The prospect of partial functions is unfortunate, with total functions much more easily dealt with.  Nevertheless, there will be cases where partial functions are convenient and important cases where they are unavoidable.

Establishment of identities is commonplace in algebra, trigonometry, introductory calculus, and other areas of early mathematical education and practice.  Identities serve to address practical questions, involve rather direct forms of proof, and can be used to find attractive computational interpretations.

These notions in the context of ‹ob› and the Miser Project become more familiar on exploration of examples.

1.1 The Blast Function

In our structure ‹ob› = 〈Ob,Of,Ot〉there is a function in Of that can be represented, using Ot, in the following fashion.

• bLast1.  ob.is-singleton( x )  ⇒ bLast( x ) = x
• bLast2. ¬ ob.is-singleton( x )  ⇒ bLast( x ) = bLast(ob.b( x ))

By reference to the definition of primitive notions given earlier, we can summarize

• bLast( x ) is the singleton that is at the end of a chain of successive ob.b( x )
  compositions, ob.b( … (ob.b( x )) … ), keeping in mind that for any singleton,
        ob.b( x ) = x.
• bLast( x ) is total -- defined for every possible definite ob, x.
• The name “bLast” was chosen to signify the determination of the ob that is at the first ob.b that makes no difference, the last ob.b in the chain.

Let ob t1 = a1 :: (a2 :: b2) :: .NIL (using the CFob canonical form for ob t1)
where a1, a2, and b2 are lindies, distinct individuals.  Then

    bLast( t1 ) = bLast( ob.b( t1 ) )
                     = bLast( ob.b( (a2 :: b2) :: .NIL) )
                     = bLast(.NIL)
                     = .NIL,

and the equational progression is typical for streamlining the progression of deductions.  At each step, exactly one of bLast1 and bLast2 apply.

1.2 The Mirror Function 

• Mirror1. ob.is-singleton( x )  ⇒ mirror( x ) = x
• Mirror2. ¬ ob.is-singleton( x ) 
       ⇒ mirror( x ) = ob.c(mirror(ob.b( x )), mirror(ob.a( x )) )

Here mirror( x ) is a form of mirror-image of the ob x.  Using ob t1 from above,

mirror( t1 )
         = ob.c(mirror((a2 :: b2) :: .NIL), mirror(a1)) )
         = ob.c(mirror(.NIL), mirror(a2 :: b2)) :: a1
         = (ob.c(.NIL, ob.c(mirror(b2), mirror(a2))) :: a1
         = ( (.NIL :: (b2 :: a2 ) ) :: a1

where these forms of identities are typical of derivations of the results for definite operands.  With experience, mixing of CFob canonical form notation in Ot expressions, as done here, is useful for readability.

The statements Mirror1-Mirror2 are by way of definition and constitute representation of the function that is characterized in this manner.  That is sufficient demonstration that there is such a function in Of, since Of is declared to include all functions on ob operands with results in Ob.  This is by definition of
    ‹ob› = 〈Ob,Of,Ot〉.

There is no inherent sense in which the mirror( x ) function has been represented correctly.  It is what it is.  I declare that representation via Mirror1-Mirror2 satisfies my intention for the function.  The decision to leave all singletons, including enclosures, intact is mine.  The use of singletons in the same manner as individuals will be common as an idiom in the crafting of functions on obs.

For mirror( x ) to provide a satisfactory mirror-image of an ob with respect to its pairings, it must satisfy the natural requirement that mirror( mirror( x ) ) = x.  That can be proven.

         ob.is-singleton( x )                                                    base case
            ⇒ mirror( mirror( x ) ) = mirror( x ) = x
         mirror(mirror( x )) = x ∧ mirror(mirror( y )) = y           induction step
               ⇒ mirror( mirror( ob.c(x, y) ) )
                     = mirror( ob.c(mirror( y ), mirror( x )) )
                     = ob.c( mirror(mirror( x )), mirror(mirror ( y ) )
                     = ob.c(x, y)                                                     
         mirror(mirror( x )) = x                                               by structural induction

This proof is by structural induction.   By design, the definition of ‹ob› primitive notions together with the partial-ordering relation ¶ satisfy the requirements for applicability of structural-induction.

1. Here, the single base case consists of all singletons and that is straightforward.
2. The induction step is by showing that when the two components of a pair satisfy the condition, so does the pair.
3. There being no other cases to cover, the conclusion follows by structural induction. 

The important consequence of having a proof, different from a demonstrative example, is that we establish the condition for all possible operands by mathematical means.

Among experts, a proof might not be exhibited for this simple case, based on the understanding that the proof is easily constructed.  Here, the objective is to illustrate the nature, purpose, and benefit of the mathematical approach and more detail is provided.

1.3 On Equivalent Function Representations

• aLast1.  ob.is-singleton( x )  ⇒ aLast( x ) = x
• aLast2. ¬ ob.is-singleton( x )  ⇒ aLast( x ) = aLast(ob.a( x ))
• blink1. blink( x ) = aLast(mirror( x ))

Here, aLast( x ) is the ob.a counterpart of bLast( x ).   blink( x ) is the same as bLast( x ) and, however  obvious that is on inspection alone, that can also be proved by deduction.

         ob.is-singleton( x )                                                     base case
             ⇒ blink ( x ) = aLast(mirror( x )) = aLast( x ) = x = bLast( x )
         aLast(mirror( y )) = bLast( y )                                     induction step
             ⇒ bink(ob.c( x, y)) = aLast( mirror( ob.c( x, y ) ) )
                     = aLast( ob.c( mirror( y ), mirror( x ) ) )
                     = aLast( mirror( y ) )
                     = bLast( y )
         blink( x ) = bLast( x )                                                 structural induction

We have demonstrated that blink and bLast, as defined above, are representations of the same function in the Of of ‹ob› = 〈Ob,Of,Ot〉.

It is commonplace to say that the functions blink and bLast are equivalent.   In rigorous speaking of the abstractness of mathematical entities it will be preferable, instead, to say that the function representations are equivalent insofar as the same function is determined.

Absent canonical forms for expression of functions in Of, assuming more about equivalent function representations is inappropriate although one might have a preference for representations that are expressive and simpler.  Demonstrations of equivalence also favor substitution of simpler representations for more complicated one.

When it comes to computational interpretations, on the other hand, there are only the function representations to work from, and derived computational interpretations may have material differences.   For example, one might prefer bLast( x )  over blink( x ), operationally (but maybe not if y = mirror( x ) is already “in-hand” and bLast( x ) is desired, making aLast( y ) more appealing).

2. Representing Other Structures: Boolean Algebras

Having data represented via encoding as obs was introduced previously.   Now we look at how one arrives at functions on such obs that honor the intended data representation.  We’ll start for the case where the representation is of some discrete structure other than ‹ob› and for which there already is a mathematical characterization.

Consider a specified abstract structure, ‹S› for which an interpretation in ‹ob› is desired.  What must be preserved by an interpretation of structure ‹S› in ‹ob› that is thereby amenable to computational-interpretation in the ‹ob› model of computation, are the essential functions of ‹S› represented in an effectively-computable form.

Boolean Algebras are mathematical structures that are interesting for computational purposes; they provide handy examples that demonstrate layering of representations and interpretations.

A characteristic of Boolean Algebras is that they apply over a variety of domains of discourse (i.e., other/related structures), yet the essential mathematical pattern of a Boolean algebra is exhibited in every case, typically in more than one way.

The axioms pertain to abstract, theoretical entities.  We can establish an effectively-computable representation directly by exhibiting function representations that are confirmed to satisfy the axiomatic specification.

2.1 ‹bp›: The Prototypical Boolean Algebra

Accomplishing effective-computability in ‹bp› given distinguished ⊥ and ⊤ offers a straight-forward interpretation in ‹ob›.   Just select two obs and corresponding representation of functions.

Restriction of the ob.NE.bp interpretation of ‹bp› in ‹ob› to two distinct Ob elements is awkward for computational-interpretation; it leaves undefined what would happen, in a computational model based on ‹ob›, when the restriction to those two operands is violated.  A remedy is offered with interpretation ob.p01.bp.

The basic technique of identifying domain elements across structures and then matching representations of primitive notions is illustrated with the ob.p01.bp interpretation of ‹bp› in ‹ob›. Careful identification of the interpretation ‹bp› in ‹ob› is akin to the approach used in demonstrating computational interpretation of ‹ob› in an SML/NJ abstract data type signature.

2.2 ‹ba›: General Boolean Algebra Representation

In what follows, the general case of Boolean Algebras on finite domains is addressed.  The treatment is more elaborate than for ‹bp›, involving the interpretation of other structures and arriving at interpretations in ‹ob› at the end.   Care is taken to identify the stages and transition from one to the next.

It is a remarkable characteristic of Boolean Algebras that many have interpretations in each other.  In consequence, there need be only a few representations of Boolean Algebras that suffice as interpretations of all the others; they will be effectively computable thereby, as well.

Here the outcome is a single ‹ob› representation, ob.bvx, that provides an interpretation for all finite Boolean Algebra cases.  The justification is essentially mathematical; ob.bvx does not make for a one-size-fits-all computational interpretation however; large-scale situations require more-elaborate computational interpretations.

We start with consideration of what are termed concrete Boolean Algebra representations: ‹bn› structures.

There is a handy means of representation of all subsets of a finite set of distinct elements.  Although not a concrete representation in itself, each representation under the scheme is isomorphic to corresponding concrete representations and thereby an entire family of Boolean Algebras.

The representation of ‹bvn› Boolean operators is abbreviated above, with the sequences all having the same length, n,  and operations extended onto corresponding pairs of list-operand elements.  The general pattern is to be understood as applying for every n.

The isomorphism of ‹bvn› with any concrete Boolean Algebra involving a set of n elements is straightforward.

Given a ‹bvn› n-tuple, X, the indicator function Ia_i( X ) determines whether a_i is a member of the corresponding (concrete) subset.

2.4 ob.bvx: One Interpretation to Hold Them All

By finding interpretation of any ‹bvn› in ‹ob›, we have represented the corresponding concrete Boolean algebra, ‹bn›, individually.  The representation ob.bvx, below, is a single formulation that provides interpretations of any ‹bn›  (and thereby, all of them) and hence all of the finite Boolean Algebras via isomorphism.

The ob.bvx representations are a bit more convoluted than the preceding ones, such as ob.p01.bp, in order to accommodate the necessary variability of interpretations without fixing n.  The trade-off is in having to develop and confirm the representation but once, rather than separately for each ‹bvn›.

Among the features of interpretation in ob.bvx, there is a canonical form that can be used in expressing individual vectors in a sometimes-compact variable-length form.

There are a few nuances to tidy up, along with considering how to tie back from ob.bvx to any ‹bvn› and thereby all of finite ‹ba› via isomorphism.

This article ends with some reflections and references to some supporting material.

Continuation

1. Interpretation, Representation, Computation, and Manifestation
   Reprise and account for specialized concepts in Miser Project, setting up for representation of the computation model

Miser Project: Representing Data as Obs

2019-11-05 Update: Complete migration from the WordPress version
2019-11-03 Update: Minor touch-ups as part of initial migration to Blogger
2018-10-18 Update: Strengthening the notion that obs can be data representations, via encoding, with such representations preserved by computational-interpretation of the obs.  Expressing canonical form is now aligned with the updated introduction in Denumerability and Effectiveness
2018-10-20 Update: Smoothing the narrative on data representation along with additional consistent use of “canonical form.”
2018-10-30 Update: Cover some loose ends about computational-interpretation of functional-notation in the OB.sig.sml selection.

The Miser Project conception is composed of a mathematical formulation along with demonstration of computational interpretations that satisfy the formulation via careful engineering.

The foundation of the conception is the mathematical structure ‹ob› = 〈Ob,Of,Ot〉that circumscribes the domain Ob with its primitive functions and an useful supply of individuals to establish mathematical counterparts of computational data.

Here continues the advance toward mathematical formulation of a theory of computation by considering the (computational) interpretation of obs as data.

Preliminaries

1. Hark! Is That a Theory I See Before Me?
2. ‹ob› Primitive Functions
3. Narrowing ‹ob› for Computational Interpretation

1. Standing in Abstraction

It is useful to entertain the notion that the ‹ob› = 〈Ob,Of,Ot〉universe of discourse consists of intangible, abstract entities: the obs (in Ob) and the (abstract) functions/predicates on obs (treated informally and jointly in Of).   Those entities have no material/concrete existence and any abstract “existence” is entirely given by ‹ob› through the logical theory, Ot.  Consider that the entities (so-called) arise entirely in language with their essential nature given by the formulation of ‹ob› expressed in the preceding installments.  Having attention on particular obs (and particular functions and predicates on them) is simply a way of speaking and not any kind of separation from ‹ob›.
  
This way of looking at the abstract nature of  ‹ob›  emphasizes that one cannot infer anything about the mathematical entities that cannot be deduced via Ot, the explicit logical-theory formulation of ‹ob›.  In particular, however closely a concrete computational interpretation manifests – gives the appearance of – ‹ob›-ness, it is important to not confuse engineered artifacts and processes with the abstractions.  Recognition of the difference is important in comprehension of how apparent layering of abstractions is achieved by computational means and software engineering.

This separation between the abstract and the apparently-operational is illustrated by the conscription of obs for interpretation as data representations.

2. Demonstrating Computational Interpretation

A demonstration computational interpretation of ‹ob› using the programming language SML/NJ has been prepared as an SML/NJ Abstract Data Type.  Possible computational interpretations are confined behind an SML/NJ signature declaration that limits what can be exercised of the computational interpretation and through which manifestation is achieved. 

The SML/NJ signature declaration is insufficient by itself.  The additional requirements for valid computational interpretations are specified in narrative comments.

The use of SML/NJ is incidental and extremely useful because of the ease with which this kind of computational interpretation can be demonstrated.   Other programming languages and methodologies will also be used.  Using this particular signature with SML/NJ and not entertaining equivalent SML/NJ alternatives is simply by convention for the SML/NJ demonstration of the ‹ob› computational model. 

To nail down this demonstration of computational interpretation, the signature is combined with definition of an SML/NJ structure that completes establishment of the valid interpretation.

Verifying validity of the interpretation depends upon knowledge of the SML/NJ language as it is applied here and upon correct operation of the SML/NJ software and the computer used.

The condition of validity is that for any deduction concerning canonical forms in Ot, the corresponding computational procedure in the interpretation is aligned by yielding the corresponding interpretation of the deduced consequence.

Even when everything is correct, it can be impacted by operational malfunctions and by resource exhaustion.   To this extent, the interpretation is contingent and empirical.  It is an accomplishment of engineering and not logic, despite the remarkable fidelity of valid interpretations in practice.

It should be clear that the establishment of interpretation validity is, in this case, dependent on inspection of the SML/NJ signature and structure and arriving at empirical agreement on their validity as a computational interpretation.  In this instance, there is a prima facie case, absent any contradictory evidence.

One subject of the Miser Project is demonstration of  validation support using mechanical deductive procedures that are themselves verified to be sound.   Understanding how that can be achieved will depend, at bottom, on a successful empirical foundation, such as that offered at the oMiser level.   It is important to confine the foundation to something whose empirical validity is readily verifiable before bootstrapping to higher levels.   The SML/NJ demonstration is exemplary in that respect.

3. Concerning Data Representation

Canonical forms can be taken as interpretations of data via an encoding – some arrangement of an ob that corresponds to a defined encoding of data.  We say the understood encoding is an interpretation of the (abstracted) data with the happy consequence that a suitably-restricted computational interpretation of the obs will preserve an interpretation as a particular representation of data. 

• That an ob has the form of a defined encoding does not imply that it is intended to be understood as such a representation ; however, when an ob fails to satisfy a defined encoding, one can conclude the ob is not such a representation.
• Whether operations on obs having the form of a defined encoding preserve the obs being such such an interpretation as data depend on how the operations honor data-interpretation-preserving restraints. 
• One way to assure that a data-interpretation is valid is by establishing functions that encapsulate the interpretation, not unlike how the interpretation of ‹ob› is accomplished via the general-purpose language, SML/NJ, using signature and structure agreements to encapsulate a computational interpretation of ‹ob›.

By way of example, one data interpretation could be as representation of numbers.  

• Let ob.NIL represent number 0,
• ob.e(ob.NIL) represent number 1,
• ob.e(ob.e(ob.NIL))) represent number 2, and so on.  

That’s mathematically adequate; it’s rather clumsy as a way of recording numeric data for any general practical purpose although we will see such elementary forms of counting in simple applications of oMiser.

A more suitable interpretation might be as a representation of numbers in a binary notation.  Let ob.NIL represent the digit 0 and let ob.e(ob.NIL) represent the digit 1, the two binary bits.  Then use

• ob.NIL as number 0,
• ob.e(ob.NIL) as number 1,
• ob.c(ob.NIL, ob.e(ob.NIL)) as number 2,
• ob.c(ob.e(ob.NIL), ob.e(ob.NIL)) as number 3, and
• ob.c(ob.NIL, ob.c(ob.NIL, ob.e(ob.NIL))) as number 4, and so on.

Here the binary representation proceeds 0, 1, 01, 11, 001, … the reverse of the usual way that binary numbers are written.  That’s still an encoding; one must look elsewhere for preference of one encoding over another.

There are many ways that encodings can be established in this manner.  Knowing what is being represented and the rule of encoding is not inherent to the obs.  Additional information on the intended interpretation is required.

It is intentional that the preceding examples be unfamiliar, exaggerating the difference between intended data and data interpretation in ‹ob›.  This is akin to the accomplishment of data representations in digital computers where the representations of data all devolve to organizations of and operations on binary bits.
  

4. Do the Lindy Hop

Although it is inescapable that additional information is required to know the intended representation for an ob’s interpretation as data, there is a simple measure to gain greater expressiveness in encodings.  We will introduce, on behalf of the computational model and for convenience, literal individuals (lindies).

Lindies are a particular class of individuals adjoined to Ob in ‹ob›.  They are simply distinct individuals with no other significance.  Any intention for them and choices among them are of no significance in ‹ob›.   Their computational interpretation, in the oMiser model, is simply as interpretations of individuals distinguished by their specific character strings.  Their intended significance in an encoding situation is similarly not addressed by ‹ob›.  Lindies are freely available to improve the expressiveness of data representations.
  

5. Streamlined Notation

Interpreting individual obs as data is accomplished on individual canonical forms, no matter how those obs might be formulated on some general pattern.   The straightforward expression of those canonical forms is aided using a specialized notation.

• A primitive individual, with name of form ending in .NAME, such as ob.NIL, is expressed as simply .NAME (e.g., .NIL).
• A lindy, designated by Ʃ's', is expressed simply s.
• ob.e( x ) is expressed ‵ ( x ), where the parentheses can be omitted when x is not a pair.
• ob.c( x, y) is expressed ( x ) :: ( y ) , where the parentheses can be omitted when x is not a pair and where the parentheses on ( y ) are always optional.
• In this notation, :: associates to the right, so abc :: .NIL :: ‵ GHI expresses the same ob as abc :: (.NIL :: ‵ GHI), which expresses ob.c(Ʃ'abc', ob.c(ob.NIL, ob.e(Ʃ'GHI') ) ).

When all optional parentheses are removed, this notation provides a direct counterpart of canonical forms which are more compact and, with practice, more understandable.  This equivalent canonical form is identified CFob.

Here is the CFob expression for an ob that might be intended as a small dictionary, with all of the terms being lindies.
    
       (English::en) :: (Русский::ru) :: (日本語::ja) :: (Français::fr) :: ‵ default

The previous examples of encodings can be streamlined using CFob expressions:

• .NIL for 0, ` .NIL for 1, ` ` .NIL for 2, … etc.
• b0 for 0, b1 for 1, b0 :: b1 for 10 (2), b1 :: b1 for 11 (3), b0 :: b0 :: b1 for 100 (4), etc., with the order of the bits in the binary-numeral representation reversed as before.
  Observe that there are two levels (at least) of representation here: first as sequences of bits and secondly the interpretations of those as (decimal) numerals.

6. In Sight of the Objective: Models of Computation

The illustration of ob-representation of data has just scratched the surface.   It is time to consider how one reasons about functions of ‹ob› = 〈Ob,Of,Ot〉and how the are considered to be effectively calculable in general and in service of data representations.  That supports unfolding the Miser Project’s applicative model of computation, oMiser.

Although there are many unexplained technicalities and additional steps to take, there is a glimpse of the objective in how intended data representations are achievable.

The mathematical structure ‹ob› = 〈Ob,Of,Ot〉incorporates an abstract model, to be introduced in subsequent articles, of algorithmic computation that demonstrates the nature of universal computation and also emphasizes how the stored-program model affords cascading manifestation -- boot-strapping -- of higher-level abstractions via software engineering.   There is a hint of that in consideration of (layers of) data representation.

We forego, for now, ideas of efficiency and expressiveness in order to first capture the essential character of stored-program computation, including how data representation and representation-honoring operations are accomplished with computational interpretations of ‹ob›.
  

Continuation

1. Representing Functions in ‹ob›’s Abstract World
   Reasoning about functions on obs and then about interpretation of other structures by representation of functions in interpretations.
2. Interpretation, Representation, Computation, and Manifestation
   Reprise and account for specialized concepts in Miser Project, setting up for representation of the computation model

Miser Project: Narrowing ‹ob› for Computational Interpretation

2019-11-05 Update: Complete Migration from the Wordpress version
2019-11-02 Update: Touch-ups with initial migration to Blogger
2019-01-19/21 Update: Be more careful with x ¶ y, referring to it everywhere as a (strict) partial-ordering.
2018-11-02 Update: Pointing out, in the Denumerability and Effectiveness portion of obtheory.txt that the partial ordering, x ¶ y, assures availability of structural induction for deductions about functions in Of.
2018-10-17 Update: Significant adjustment of canonical form notions in the obtheory.txt on Denumerability and Effectiveness.

Preliminaries

1. Hark! Is That a Theory I See Before Me?
   The first-order logic with equality notation for Ot, the mathematical theory for ‹ob›
2. ‹ob› Primitive Functions
   Mathematical characterization  of four primitive functions and allied primitive notions that establish the domain of discourse, Ob, in structure ‹ob› = 〈Ob,Of,Ot〉

1. Primitive Notions

All of the apparatus for characterizing the mathematical structure ‹ob› = 〈Ob,Of,Ot〉has been used, so far, to present a simple universe of discourse, Ob and essential characteristics of that universe in terms of its primitive individuals, enclosures, and pairs.

• primitive individuals
  that are introduced simply by being uniquely-named in form ob.NAME, with ob.NIL given so far (although non-primitive individuals will be introduced by other means)
• enclosures
  signified by terms of form ob.e( x ) where x is any ob and ob.e( x ) is the unique ob that encloses that x.
• pairs
  signified by terms of form ob.c( x, y ) where x  and y are any obs and ob.c( x, y ) is the unique ob consisting of the pairing of the particular x and y.

Each ob is fashioned as exactly one of those (so far).  The primitive notions also provides mathematical means for discerning conditions that an ob satisfies. 

• If z = ob.c(x, y) then x = ob.a( z) and y = ob.b( z )  and also x ≠ z and y ≠ z
• If z = ob.e( x ) then x = ob.a( z ) and z = ob.b( z ) and also x ≠ z
• If z is an individual then z = ob.a( z ) and z = ob.b( z ).

These conditions are sufficient to provide predicates that discriminate the flavor of any ob.

• ob.is-pair( z ) is true if an only if neither of ob.a( z ) and ob.b( z ) are z, which simplifies to ob.b( z ) ≠ z
• ob.is-singleton( z ) is true if and only if ¬ ob.is-pair( z ), which simplifies to ob.b( z ) = z
• ob.is-enclosure( z ) is true if an only if ob.is-singleton( z ) and ob.a( z ) ≠ z
• ob.is-individual( z ) is true if and only if z = ob.a( z )

Note that there is no ob, z,  for which z = ob.a( z ) with ob.b( z ) ≠ z and that will never change.
This informal description is consistent with the rigorous treatment expressed in the notation for Ot.
  

2. Informal Terminology

The function names ob.a, ob.b, ob.c, and ob.e are not particularly suggestive of anything.  In that respect, it is the theoretical characterization of them that gives their essential significance, make of it what we might.  That is intended.

In contrast, the terms individual, singleton, enclosure, and pair are suggestive of some intended significance beyond merely what there is to be gleaned from Ot alone.

It is the case that certain idiomatic purposes are reflected in the choice of those names.  It is important to appreciate that, theoretically, the chosen names are irrelevant despite their outside-of-the-mathematical-theory hinting of an intended application of ‹ob›.  There will be more of this.  It is important to keep in mind that such “intended interpretation” is more about why ‹ob› is formulated the way it is; it doesn’t qualify what the ‹ob› structure is, mathematically.  The mathematical entities involved are solely what is discernable from the characterization in Ot.
  

3. Positioning for Computational Interpretation

There is more to be said in conjunction with the primitive notions for drawing a solid connection with computation.

• Denumerable.  The obs can be counted and there are exactly as many of them as there are natural numbers, given by the progression 0, 1, 2, …, n, n+1, … .
• Effective. Ot characterizations of functions, F, in Of are such that deduction of F( x )  for x a given ob is tantamount to a procedure for computation of at most one particular ob y for which y = F( x ) and x is any specific ob. 
• Strict Partial-Ordering. Structural induction available for deductions concerning the representation in Ot of functions in Of.  This has obs be finite with every ob having a finite canonical form in Ot.

To accomplish that, the textual definition of ‹ob› in file obtheory.txt is extended.

Continuation

1. Representing  Data as Obs
   Expanding on the difference between a logical mathematical theory and computational interpretation, noticing that obs themselves can be interpretations of data, that interpretation being carried over to a computational interpretation.  SML is used to demonstrate one operational interpretation in a programming language.
2. Representing Functions in ‹ob›’s Abstract World
   Reasoning about functions on obs and then about interpretation of other structures by representation of functions in interpretations.
3. Interpretation, Representation, Computation, and Manifestation
   Reprise and account for specialized concepts in Miser Project, setting up for representation of the computation model

Miser Project: ‹ob› Primitive Functions

2019-11-05 Update: Complete migration from the WordPress post
2019-11-02 Update: Tiny edits and migration to Blogger

Preliminaries

• Hark! Is That a Theory I See Before Me?
  The first-order logic with equality notation for Ot, the mathematical theory for ‹ob›

Characterizing the mathematical structure ‹ob› = 〈Ob,Of,Ot〉involves first-order-logic with equality as the project notation for expressing  an applied logic, Ot, in which Ob is the entire domain of discourse.   Predicates and functions (in Of) are also introduced by characterization in Ot.

Four distinct functions, along with equality, are sufficient to distinguish among all of the Ob obs.  It will be the case that characterization of obs, including as transformations of other obs, will reduce to compositions of these functions and cases of equality/inequality.

The notions of individual, enclosure, singleton, and pair have their inspiration in the nested array work of Trenchard More and  the foundation structure of LISP by John McCarthy.  It is intentional that these structural characteristics are limited and simple.

An essential characteristic is that the primitive notions have the structure be closed and the primitives be total.  One cannot in any way “fall out” or “fall through” a primitive.  And if the operands are defined, so are the results, viewing the primitives as operations.  This tidiness will be valuable in demonstrating and reasoning about practical computational interpretations of the mathematical entities of ‹ob›.

The elaborate treatment of just this much is also indicative of how much one must assert to narrow the objects of discourse to ones that are suitable for underlying a model of computation.  And we are not quite there yet.

At this point, consider that mathematical treatment is rather different than construction of computer programs that embody a mathematical theory in some sense.   It is one purpose of The Miser Project to sharpen and clarify that condition.
  

Continuation

1. Narrowing  ‹ob› for Computational Interpretation
   Summarizing the primitive notions and positioning for computational interpretation with additional restraints
2. Representing Data as Obs
   Expanding on the difference between a logical mathematical theory and computational interpretation, noticing that obs themselves can be interpretations of data, that interpretation being carried over to a computational interpretation.  SML is used to demonstrate one operational interpretation in a programming language.
3. Representing Functions in ‹ob›’s Abstract World
   Reasoning about functions on obs and then about interpretation of other structures by representation of functions in interpretations.
4. Interpretation, Representation, Computation, and Manifestation
   Reprise and account for specialized concepts in Miser Project, setting up for representation of the computation model

Miser Project: Hark! Is That a Theory I see Before Me?

2019-11-05 Update: Complete separation from the Wordpress posts
2019-10-31 Update: Tidy up to reflect the latest status and how to find archived forms.
2019-10-30 Update: Migrate from Wordpress to Blogger with elimination of advertising.  Comments will not carry over (no loss).  Some touchups to reflect abandonment of Hexo as a blog-production platform.
2019-01-18 Update: Introduce the latest 0.2.5 obtheory.txt prelude and notation section with corrections and improved text.
2018-10-24 Update: Corrected definition of  ¬ p in the notation. (Yikes)

My 2018 plan was to have a stable experimental setup at the Spanner Wingnut blog, preceding systematic revival of my permanent, persistent blogs.  My agitation over the restoration of blogging and the use of hexo to generate static server pages reflected my anxious desire to restore Numbering Peano, the blog devoted to The Miser Project and related theoretical topics.  As of October 2019, I am giving up on that approach, and also replacing the use of a free Wordpress account with this free Blogger account.  I am migrating the important current work first.

I had begun writing about my capstone career project on a Facebook Page and on GitHub, where there are also preliminary (mock-up) demonstrations of implementation.  Issues on the GitHub project have been used to address questions and provide preliminary documentation.

At the moment, documentation is in plain-text files on GitHub.  That may continue as an ultimately-dependable form of persistent record.   Each version of a file is identified with a link to the location of the latest version, as in the prolog of file obtheory.txt here.

Mathematical notation is confined to text and the use of Unicode encoding of the text.   Without mathematical-notation support for blog pages, the most reliable means of presenting the plain-text form on the web is via images.

Having web pages and others, expressed in HTML notation, allows for greater expressive power.  Text has, within its limitations, useful control over layout.  We’d like both, and while wrestling to get generated blog pages in a stable form, with support for mathematical formulas, the use of screen captures here is the workaround.

Continuation

1. ‹ob› Primitive Functions
   Mathematical characterization  of four primitive functions and allied primitive notions that establish the domain of discourse, Ob, in structure ‹ob› = 〈Ob,Of,Ot〉
2. Narrowing ‹ob› for Computational Interpretation
   Summarizing the primitive notions and positioning for computational interpretation with additional restraints
3. Representing Data as Obs
   Expanding on the difference between a logical mathematical theory and computational interpretation, noticing that obs themselves can be interpretations of data, that interpretation being carried over to a computational interpretation.  SML is used to demonstrate one operational interpretation in a programming language.
4. Representing Functions in ‹ob›’s Abstract World
   Reasoning about functions on obs and then about interpretation of other structures by representation of function in interpretations.
5. Interpretation, Representation, Computation, and Manifestation
   Reprise and account for specialized concepts in Miser Project, setting up for representation of the computation model