Abstract
We show how to regard covered logic programs as cellular automata. Covered logic programs are ones for which every variable occurring in the body of a given clause also occurs in the head of the same clause. We generalize the class of register machine programs to permit negative literals and characterize the members of this class of programs as n-state 2-dimensional cellular automata. We show how monadic covered programs, the class of which is computationally universal, can be regarded as 1-dimensional cellular automata. We show how to continuously (and differentiably) deform 1-dimensional cellular automata from one to another and understand the arrangement of these cellular automata in a separable Hilbert space over the real numbers. The embedding of the cellular automata of fixed radius r is a linear mapping into R22r+1 in which a cellular automaton's transition function is the attractor of a state-governed iterated function system of affine contraction mappings. The class of covered monadic programs having a particular fixed point has a uniform arrangement in an affine subspace of the Hilbert space ℓ2. Furthermore, these programs are construable as almost everywhere continuous functions from the unit interval {x
| Original language | English (US) |
|---|---|
| Pages (from-to) | 153-186 |
| Number of pages | 34 |
| Journal | Annals of Mathematics and Artificial Intelligence |
| Volume | 21 |
| Issue number | 2-4 |
| State | Published - 1997 |
Fingerprint
ASJC Scopus subject areas
- Artificial Intelligence
- Applied Mathematics
Cite this
A continuum of discrete systems. / Blair, Howard A.; Chidella, Jagan; Dushin, Fred; Ferry, Audrey; Humenn, Polar.
In: Annals of Mathematics and Artificial Intelligence, Vol. 21, No. 2-4, 1997, p. 153-186.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - A continuum of discrete systems
AU - Blair, Howard A.
AU - Chidella, Jagan
AU - Dushin, Fred
AU - Ferry, Audrey
AU - Humenn, Polar
PY - 1997
Y1 - 1997
N2 - We show how to regard covered logic programs as cellular automata. Covered logic programs are ones for which every variable occurring in the body of a given clause also occurs in the head of the same clause. We generalize the class of register machine programs to permit negative literals and characterize the members of this class of programs as n-state 2-dimensional cellular automata. We show how monadic covered programs, the class of which is computationally universal, can be regarded as 1-dimensional cellular automata. We show how to continuously (and differentiably) deform 1-dimensional cellular automata from one to another and understand the arrangement of these cellular automata in a separable Hilbert space over the real numbers. The embedding of the cellular automata of fixed radius r is a linear mapping into R22r+1 in which a cellular automaton's transition function is the attractor of a state-governed iterated function system of affine contraction mappings. The class of covered monadic programs having a particular fixed point has a uniform arrangement in an affine subspace of the Hilbert space ℓ2. Furthermore, these programs are construable as almost everywhere continuous functions from the unit interval {x
AB - We show how to regard covered logic programs as cellular automata. Covered logic programs are ones for which every variable occurring in the body of a given clause also occurs in the head of the same clause. We generalize the class of register machine programs to permit negative literals and characterize the members of this class of programs as n-state 2-dimensional cellular automata. We show how monadic covered programs, the class of which is computationally universal, can be regarded as 1-dimensional cellular automata. We show how to continuously (and differentiably) deform 1-dimensional cellular automata from one to another and understand the arrangement of these cellular automata in a separable Hilbert space over the real numbers. The embedding of the cellular automata of fixed radius r is a linear mapping into R22r+1 in which a cellular automaton's transition function is the attractor of a state-governed iterated function system of affine contraction mappings. The class of covered monadic programs having a particular fixed point has a uniform arrangement in an affine subspace of the Hilbert space ℓ2. Furthermore, these programs are construable as almost everywhere continuous functions from the unit interval {x
UR - http://www.scopus.com/inward/record.url?scp=21944445206&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21944445206&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:21944445206
VL - 21
SP - 153
EP - 186
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
SN - 1012-2443
IS - 2-4
ER -