> If you fix a bound on memory, i.e. take infinity out of the question, maybe you can't construct such machines.

A Turing machine with a tape of only constant length is equivalent to a finite-state automaton. If the length of the tape is a linear function of the length of the input, on the other hand, the machine is a linear bounded automaton.

https://en.wikipedia.org/wiki/Linear_bounded_automaton

https://en.wikipedia.org/wiki/Finite-state_machine

https://en.wikipedia.org/wiki/Template:Formal_languages_and_...