COMPUTER SCIENCE COLLOQUIUM
 

                       FRIDAY, AUGUST 23, 2002
 
                     EDUCATION BUILDING ROOM 226
 
                   TIME: 1:50 (DONUTS) 2:00 (TALK)




Loops & Complexity in Digital Systems

          Gheorghe Stefan

Visiting Professor St. Mary's College of MD
Professor at University Politehnica of Bucharest
email: gmstefan@smcm.edu
http://mathres1.smcm.edu/~george/

When the number of components on the chip is over a million, the complexity,
not the size is the main problem faced by the designers. The Kolmogorov -
Chaitin complexity of a circuit is the size of its definition and the
interplay between size and complexity is captured by closed loops inside a
digital system. We propose an approach for classifying digital systems which
takes into account the number of loops they contain. The number of loops
induces a hierarchy, where combinational circuits correspond to no-loop
circuits, memories to one-loop circuits, automata to 2-loop circuits,
processors to 3-loop circuits, computers to 4-loop circuits,..
self-organizing structures to n-loop circuits. Each new loop increases the
autonomy, allowing new functional features: memorizing, sequencing,
controlling, interpreting,..., self organizing. We relate the resulting
hierarchy to other classical theories: recursive function theory, formal
language and information theory. To compute any partial recursive function a
system must have at least three loops. A correspondence between the number
of loops and Chomsky's hierarchy is exhibited.

------------------------------------------------------------
The second talk will follow immediately:

Mihaela Malita
St. Mary's College of Maryland
Email: mmalita@smcm.edu
http:// mathres1.smcm.edu/~mihaela

Logical Puzzles in Prolog

Logical programming languages provide a good framework for solving logical
puzzles. I will present how to use Prolog to solve some classical puzzles:
The Zebra Problem, The 8 Queen Problem and other examples from Dell's: Math
Puzzles Logic Problems, 2001. In order to solve those puzzles a tool library
of Prolog predicates has been used and will be presented. This analysis will
provide the framework for actually building an expert system for solving
those puzzles.