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.
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.