|
|
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:
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.
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
n140401b: Pursuing Generality [latest]
n140401c: Grounding
Barwise, Jon (ed.). Handbook of Mathematical Logic. Elsevier (Amsterdam: 1977). ISBN 0-444-86388-5 pbk.
Copeland, B. Jack, "The Church-Turing Thesis", The Stanford Encyclopedia of Philosophy (Fall 2008 Edition), Edward N. Zalta (ed.), available at <http://plato.stanford.edu/archives/fall2008/entries/church-turing/>.
Rosenbloom, Paul. The Elements of Mathematical Logic. Dover Publications (New York: 1950).
Wikipedia. Church-Turing Thesis (article). 2014-04-19T03:42 version at <https://en.wikipedia.org/w/index.php?title=Church%E2%80%93Turing_thesis&oldid=604830212>. Accessed on 2014-04-27.
n001000: Miser as Theoretical Model
n010201: Manifest Abstractions
n010207: What's an Algorithm?
n020300: Evolution of
Ob Structure
n140401a: Diary & Job Jar
 |
|
created 2014-04-27-08:02 -0700 (pdt) by
orcmid |