| There are three main results in this dissertation. They are PLS-completeness of discrete Hopfield network convergence with eight different restrictions, (degree 3, bipartite and degree 3, 8-neighbor mesh, dual of the knight's graph, hypercube, butterfly, cube-connected cycles and shufffe-exchange), exponential convergence behavior of discrete Hopfield network, and simulation of Turing machines by discrete Hopfield Network.; We explored lower bounds on the convergence time of discrete Hopfield networks by constructing binary counters which have transients of length {dollar}2sp{lcub}n/4{rcub}{dollar} for sequential mode and {dollar}2sp{lcub}(n-1)/7{rcub}{dollar} for parallel mode. Most of all, we made the connection network of all counters planar and of constant degree. These counters not only are the evidence of exponential convergence of discrete Hopfield Networks but also can be used as a clock generator.; Finally, we perform real time simulations on both Deterministic Turing machine and Non-Deterministic Turing machine directly with discrete Hopfield networks which derived new upper bounds for size and time. |
