ON DYNAMIC SWITCHING IN ONE-DIMENSIONAL ITERATIVE LOGIC NETWORKS
MONTANA STATE COLL BOZEMAN
Pagination or Media Count:
A SITN is a cascade of identical finite automata such that the ith power automation receives an x sub i input from the outside world and a y sub i input from its left neighbor, and produces a z sub i output to the outside world and a y sub il output to its right neighbor. We prove three main theorems 1 For every integer k there is a cell definition such that a corresponding SITN either can or cannot switch from equilibrium to a cycling condition following a single x sub i change according as n equal to or less than k or n k, respectively 2 there do not exist algorithms to tell whether or not a given cell definition admits of a SITN that can start from equilibrium and following a single x sub i change either a switch into a cycling con dition, or b put out a z sub i 1 during a switching transient and 3 there do not exist algorithms to tell whether or not a given SITN cell definition must have every switching transient following a single x sub i change from equilibrium either a die out a bounded number of cells to the right of the change, or b extend all the way to the SITN boundary. All theorems are proved constructively on finite-state diagrams, and 2 and 3 hinge on an embedding of Minskys Post Tag system results into such diagrams. We conclude with several iterative network equivalence demonstrations.
- Computer Systems Management and Standards