Turing Machines with Finite Memory

Wilson Rosa de OliveiraMarcílio Carlos Pereira de SoutoTeresa Bernarda Ludermir

Motivated by our earlier work on Turing computability via neural networks[4, 3] and the results by Maass[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.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: