loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
VII Brazilian Symposium on Neural Networks (SBRN'02)
Turing Machines with Finite Memory
Pernambuco, Brazil
November 11-November 14
ISBN: 0-7695-1709-9
Motivated by our earlier work on Turing computability via neural networks[4, 3] and the results by Maass et.al.[14, 15] on the limit of what can be actually computed by neural networks when noise (or limited precision on the weights) is considered, we introduce the notion of Definite Turing Machine (DTM) and investigate some of its properties. We associate to every Turing Machine (TM) a Finite State Automaton (FSA) responsible for the next state transition and action (output and head movement). A DTM is TM in which its FSM is definite. A FSA is definite (of order k > 0) if its present state can be uniquely determined by the last k inputs. We show that DTM are strictly less powerful than TM but are capable to compute all simple functions([1]). The corresponding notion of finite-memory Turing machine is shown to be computationally equivalent to Turing machine.
Citation:
Wilson Rosa de Oliveira, Marcílio C.P. de Souto, Teresa B. Ludermir, "Turing Machines with Finite Memory," sbrn, pp.67, VII Brazilian Symposium on Neural Networks (SBRN'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.