Registered: Sep 2003
Posts: 5

Symbolic systems are rule-based systems of the form
Nest[# /. lhs -> rhs &, init, steps] where the lhs is an expression like e[x_][y_] and the rhs something like
x[x[y]]. Initial conditions (init) are like e[e][e[e[e]e]e[e]

These systems can present considerable complexity, but they are different from Cellular Automata in the sense that they evolve in a largely non-local way.

For symbolic systems, see NKS 102-104 and 896-898, and NKS Open Problems(.pdf), pp. 26-27

The so called SK-combinators invented by Schönfinkel are an example of symbolic system with two rules. SK-combinators are capable of universal computation. For details, check NKS 711-714 and 1121-1123.

Last edited by Fred Meinberg on 04-21-2004 at 01:01 AM

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 551

Fred,

I don't know if you're still around, but I have
some interest in this subject, especially as it
relates to the "propositions as types" (PAT)
analogy and the question of whether there
is a PAT analogy for classical logic.

Jon Awbrey

Report this post to a moderator | IP: Logged

Registered: Sep 2003
Posts: 5

Jon,

Symbolic systems generalize combinators (what I did in the NKS SS 2003, and will present at NKS 2004, is basically running one-combinator systems with different rules, different initial conditions, and different evaluation schemes.) So, if combinators are relevant for the PAT question, symbolic systems will be.

(see also: NKS p. 898 )

Fred Meinberg

Last edited by Fred Meinberg on 06-19-2004 at 12:53 PM

Report this post to a moderator | IP: Logged