569 views
0 votes
0 votes
Whether a TM has finite number of states?

Decidable or undecidable??

2 Answers

Best answer
2 votes
2 votes
There is no possibility for a TM to have infinite number of states; so the problem is a trivial one and for any trivial problem decidability is straightforward.

Now, even if the problem is whether a given TM is having $10$ states (or any constant), it becomes a non-trivial problem of Turing machines (not of recursively enumerable set and hence Rice's theorem is not applicable) but is still decidable. Because to decide this all we need to do is to decode the TM description and just count the number of states. This is similar to answering if a given $C$ program is having $100$ lines of code.
selected by

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
141 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
142 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?