Some computational problems do not operate over concrete data types, or even on abstract data type. Instead, they operate over a much more abstract framework, that being on models of computation. Showing that these problems are decidable is vital in theoretical compute science, as if they are not, any concrete model (such as a physical computer) can never hope to solve it, no matter how powerful it is.
- Acceptance Problem
- Emptiness Problem
- Equivalence Problem
- (Turing Machine Only) Halting Problem