Self Doubt on Decidability

Question

Here in this video https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87 professor is explaining that Turing Machine that  accept something is recursively enumerable. We would run multiple inputs on turning machine in parallel using dovetailing technique (where If first input to turning machine has been simulated for 5 steps, the second input would have been simulated for 4 steps) and would eventually get to know If Turning Machine accepts something if it does and hence recursively enumerable.

But in the same lecture he is telling that Turning Machine that accept only one string is not recursively enumerable. Shouldn't this also be recursively enumerable based on the procedure explained for above example ? If there are even two strings that are being accepted won't we get to know using the same method ?

Answer 1

Not RE. A machine that accepts only one string has this interpretation:

1. Accepts one string

2. Rejects all other strings

It is part 2 that makes it not RE. Because in order to check if part 2 is satisfied, we will have to check all the possible strings to make sure there's no violation (and the no of strings is infinite) and thus even for the 'Yes' case we don't have a procedure which can halt in a finite amount of time. Hence this makes it not RE.

Comments

Got your point that we would never be able to say that turning machine accepts only one string. Thanks