Decidability

Question

"TM takes more than 481 steps on some inputs "

Agree : If given set of input alphabets are finite say over {a,b} then we have to check for only finite inputs (may be large in size ). --> Decidable.

Disagree : What if given input alphabet set itself it is infinite. Say over set of natural numbers
{1,2,… } then cases that we have to check for will not be finite as per me. If someone say lets check these many strings over these given alphabets then I may increase my alphabet set as its infinte hence it will also increase the possible strings which we have to check.
—> Decidable or Undecidable ?

Comments

@Headshot

Please share the link of one of such questions. I'm sure their relevance would be different and clear.

---

@HeadShot

Though i am not well versed in this topic but if you provide me a link about the doubt you mentioned in your comment then i can try to help..

As of now I can recall one kind of question that says whether all possible languages over (0,1)* is countable or not. Here the input set is finite but set of all possible languages on it is uncountable [Prove by Cantor diagonalization]

If it is asked if set of all strings on (0,1)* is countable or not then the ans. is it is countable  (countably infinite).

---

@MiNiPanda

Hey, thanx . It is helpful :)