ON DYNAMIC SWITCHING IN ONE-DIMENSIONAL ITERATIVE LOGIC NETWORKS
Abstract
A SITN is a cascade of identical finite automata such that the i(th) 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 Minsky's Post Tag system results into such diagrams. We conclude with several iterative network equivalence demonstrations.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1963
- Accession Number
- AD0408414
Entities
People
- W. L. Kilmer