[ctoa]

There remain undecidable problems even with finite memory/state space.

Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:

Emptiness: Does an LBA reject all possible inputs? Universality: Does an LBA accept all possible inputs over its alphabet? Equivalent: Do two LBA accept the same language? Finiteness: Does an LBA accept a finite number of strings.