The Miser Project

Notes Folio n140401
Pursuing Generality

miser>notes>
2014>04>

n140401>
0.00 2017-09-26 11:20


Although oMiser is a miniature computational mechanism in its simplicity, it is offered as serious demonstration of ambitious reach: universal general-purpose computing power.

We begin with the structure, ‹ob› including a set of constructions, the Obs.  This structure is carefully defined to establish that it is amenable to manifestation by procedures operating in a conventional digital computer.  There is a kind of arithmetic that can be carried out with Obs and there are many ways to manifest arithmetic as we know it.

The next step is demonstration that there is a function on two Obs, ob.ap(p, x) that is a Universal Function for ‹ob›, with Ob p  taken as the description of a procedure that ob.ap applies, given operand Ob x, to produce a result Ob y.  The thesis is that for every function f that is computable on Obs x, there are  Obs p such that ob.ap(p, x) = f(x).  And the function ob.ap is itself computable.  oMiser implementations using computer programs demonstrate the computational manifestation of ob.ap.

The importance of ob.ap universality for ‹ob›  is that it is also Church-Turing complete in the sense that at least the functions representable under the Church-Turing thesis are representable via suitable constructions of p and interpretations of x and y such that ob.ap(p, x) = y.  

The universality of ob.ap is not easy to exploit, without some generalized means to express Obs as data (the x) and as procedures (the p) to which ob.ap is applied.  The Frugal notation and the oFrugal program facilitate the useful expression and manipulation of Obs via an oMiser mechanism.

To bridge from working "merely" on Obs, there are two intermediate steps that facilitate bridges to representation of (computable) functions on other domains:

  1. Representation of other structures having finite elements via representation in terms of Obs and functions on those Obs that correspond to sufficient primitive functions of the intended structure, paralleling ‹ob› but realizing some other structure such as the Peano Arithmetic, ‹pa›.  This is tantamount to usage of ‹ob› to represent other abstract data types.
      

  2. Demonstration that the structure of combinators, ‹c›, already represented, is automatically extended to representations of other structures, as in (1), to deliver all computable functions of (1) simply by employing the primitive procedures for representation of (1) along with combinator procedures, and ob.ap.

In this way, the extension to computationally-complete representations of other structures is accomplished using the machinery that is already achieved with ob.ap and ‹ob›.

At this point, the embrace of generality branches along a number of lines.  .

{Ed.Note: To be Continued ...}

-- Dennis E. Hamilton
Seattle, Washington
2014-04-27

Related Material


0.00 2014-04-27-08:02 Create Placeholder
An initial page was created as a container for later introduction of content beyond the summary of initial steps.

Construction Structure (Hard Hat Area)

You are navigating the Miser Project.

created 2014-04-27-08:02 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 17-09-26 11:21 $
$$Revision: 33 $