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

In all the cases it is decidable.

I hope you know about the finite case.

For infinte... You are saying that what if alphabet set is infinite? Right?.

 

Bro, neither alphabets can be infinite, nor the string you are giving as an input can infinte... Where have you heard that a machine is taking a never ending input string??

Formal definition of strings and alphabets.

Alphabets: finite set of legal symbols used to form strings.

String: finite sequence of symbol from that alphabet.

You doubt was related to the infinteness of the alphabets, so now I hope it's clear.

---

@aambazinga

Yeah, thanx.

But in GATE they sometimes argue on infiniteness of set and inpute length then shoudl I "always" discard such option ?

---

@MiNiPanda

---

@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 :)