1
$\begingroup$

The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical literature.

In reference to the Chomsky hierarchy (and automata), which is the linear feedback shift register languages/automaton ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It has a finite memory, so it's just a DFA (or some of the output-producing variants). If you allow a growing/shrinking feedback register, it is probably equivalent to a Turing machine.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The linear feedback shift register not allow rowing/shrinking , but it is an interesting information. Why do you think that growing / shrinking can make turing equivalent ? Do you have any scientific paper or link that you can send me? $\endgroup$
    – Claudio Martines
    Commented Mar 21, 2014 at 18:59
  • $\begingroup$ @ClaudioMartines, as I say in my answer, the number of configurations is finite, and they are related by a function. There is a starting configuration, a definite input alphabet, and a set of accepting configurations. This is just a roundabout way of describing a DFA. What distinguishes a Turing machine is precisely that the amount of information it can keep in its tape is unbounded. $\endgroup$
    – vonbrand
    Commented Mar 21, 2014 at 19:09
  • $\begingroup$ Thank you for your response. One question: if the register contains natural numbers and if there exist an algorithm (consisting only of logic xor gates) can cover all N, could i say that it is Turing equivalent ? $\endgroup$
    – Claudio Martines
    Commented Mar 21, 2014 at 19:17
  • $\begingroup$ @ClaudioMartines, in the moment you allow unlimited natural numbers into your automaton, it is a safe bet that it is equivalent to a Turing machine (just two unlimited integers, testing for zero, adding and substracting 1 under the control of a finite "program" is enough). $\endgroup$
    – vonbrand
    Commented Mar 21, 2014 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.