# Understanding decidability

Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course.

1) I am reading why the language AFDA is decidable and why ATM (halting problem) is not. The explanation says that the emulated TM in ATM might loop forever. I agree, because a specific input string might make the TM going forever, always able to apply rules and never halting.

However, why is AFDA decidable? What if the automaton never reaches any of its final states and keeps looping? There might be a specific input that makes the FDA never reach such states. I understand that once the input string finishes, it will be either accepted or rejected, but what if it does not finish? I'm assuming the input string in the TM can be infinite.

2) The same problem I have here:

A = { 0^k 1^k | k >= 0}


This language is decidable, and it will halt in strings like 10, 010101, etc but what if the input string is infinite 01010101...... it will never end.

What am I missing?

• I am sorry but I originally published it in StackOverflow where I saw plenty of questions about TMs. Then I was sent here... then now you -1 my question and send me to Computer Science... Nobody agrees. I think my question is strongly related to theoretical computer science, though... – Bea Mar 5 '14 at 19:46
• no dispute that this relates to theoretical computer science. However, it's the "level" of the question that places it in CS.SE. I'm sorry that SO moved you here: they should have moved you straight to CS.SE – Suresh Mar 5 '14 at 19:56
• Yes, thanks. I read the help center and I agree the question does not belong here. I did not even know about this site, but this is what I was told in SO... Sorry about that – Bea Mar 5 '14 at 19:58
• too many acronyms around ... I have done quite a bit of automata theory, but I do not recall seeing AFDA before. – babou Mar 6 '14 at 13:13

2) Inputs are always finite strings. There are generalizations of finite automata ($\omega$-automata of various kinds [Buchi, Rabin, Muller]) that accept $\omega$-words (countably infinite strings) as inputs.