In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg
Essentially, Pushdown Automata (PDA) can solve more problems (i.e. recognize more languages) than Finite State Machines (FSM), Turing machines (TM) can solve more problems than PDA etc. To continue, suppose $s(FSM), s(PDA), s(TM)$ denotes the set of problems solved by FSMs, PDAs and TMs, respectively. Then, the figure states that: $s(FSM) \subset s(PDA) \subset s(TM)$
However, I have a confusing argument regarding the cardinality of the above sets.
- All sets of computational models (e,g, FSMs, PDAs and TMs) are countably infinite. Because all can be represented as computer programs in binary string form, which are also countably infinite.
- If FSMs are countably infinite, then the problems that can be solved with FSMs, $s(FSM)$, cannot be more than countably infinite. The same is true for $s(PDA)$ and $s(TM)$.
- Countably infinite sets have cardinal number $\aleph_0$ (aleph zero). Thus if $C(.)$ denotes cardinality, $C(s(FSM)) = C(s(PDA)) = C(s(TM)) = \aleph_0$.
Is the above argument correct? If it is true and the above sets have the same cardinality, in what sense is the figure (which states that $s(FSM) \subset s(PDA) \subset s(TM)$ true?
The only hypothesis I can think of is an argument of "redundancy". That is that while there is an equal number of TMs and FSMs, the same is not true for the problems that can be solved with these. That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent. Thus, more problems can be solved with TMs than can be with FSMs. Stated differently, the set of problems solved by TMs is greater than the problem set solved by FSMs. However, both problem sets are infinite and there is no infinity smaller than $\aleph_0$, so the two problems sets should have the same cardinality $\aleph_0$