Question

Computer Science:
Please be sure to make sure answer is legible if answer is written. :)

Prove that a complement of any finite set of binary strings F has a decidable membership. Will such F always be recursive?

Answer 1

To prove, that the membership in the complement of a finite set of binary string F is decidable, argue as follows.

Consider the set of finite strings F. A Turing machine that decides F can be constructed as follows. The set of finite strings can be hardcoded in the states of the Turing machine. In fact, the set of finite strings can be encoded even into a Finite automaton. On each string, the machine will take a unique sequence of states, and end up at a state corresponding to that string. Note that the number of strings to "remember" is finite, hence there will be a finite number of states.

In this way, a halting Turing machine can be constructed which accepts exactly the set of strings in F. Now this can be complemented as follows. Exchange the final states with the non-final states. Then a word in the new machine will be accepted if and only if it was rejected in the previous machine. Therefore this machine will now accept the complement of F.

This proves that the complement of F has decidable membership. Note that the construction above already constructs a halting Turing machine for F. Therefore it already proves that F is recursive.

Comment in case of any doubts.

EDIT: Adding mathematical notation as asked. Let the words in F be . The machine has a starting state .  For the word , create the states . Add the transitions and . Add the state to the set of final states. Do this for each word . All the missing transitions go to the "reject" state. The machine thus created will accept the language which is exactly F.

This machine can be inverted as follows. Let the set of states be and the set of final states be . Create a new machine with the same transitions, the same set of states, and keep as the final states in the machine. If the old machine accepts F, then the new machine will accept as desired.