Question

Theorem: a* b is decidable

Proof: By contradiction; assume a*b is decidable. Let D be a decider for it. Consider what happens when we run D on a String of infinitely many a’s followed by a b and on a string of infinitely many a’s. Let’s call this first string x and the second string y. Since D is a decider, it halts on all inputs, and therefore cannot run for an infinitely long time.

Therefore D must halt before reading the last character of x and the last character of y, but y is not in the language a*b. Otherwise, D rejects x, but x is in the language a*b.

Answer 1

Solution:

Proof: By contradiction; assume a*b is decidable. Let D be a decider for it. Consider what happens when we run D on a string of infinitely many a's followed by a b and on a string of infinitely many a's. Let's call this first string x and the second string y. Since D is a decider, it halts on all inputs, and therefore cannot run for an infinitely long time. Therefore, D must halt before reading the last character of x and the last character of y. Because x and y are the same except for their last character, we see that D must have the same behavior when run on x and when run on y. If D accepts x, then D also accepts y, but y is not in the language a*b. Otherwise, D rejects x, but x is in the language a*b. Both cases contradict the fact that D is a decider for a*b. We have reached a contradiction, so our assumption must have been wrong. Thus a*b is undecidable.

What's wrong with this proof?

By definition, all strings must have finite length, so there's no such thing as an infinite-length string. Therefore, the strings x and y described here don't actually exist, so you can't run D on those two strings at all.