# How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem :

B={ x | there exists a prefix of x that is in A}.

Show that B is semi-decidable. In other words, you need to describe an algorithm M that on input a string x semi-decides if some prefix of x is in A (“semi-decides” means that it is OK if the algorithm loops for strings with no prefix in A). You will assume that you have an algorithm MA that semi-decides A.

Any help would be greatly appreciated!

You are given that $$A$$ is semi-decidable. Therefore there is a Turing machine $$M$$ that halts on an input $$x$$ iff $$x \in A$$. Your goal is to construct another Turing machine $$M'$$ that halts on an input $$x$$ iff one of the prefixes of $$x$$ is in $$A$$. In other words, $$M'$$ should halt on $$x$$ iff $$M$$ halts on one of the prefixes of $$x$$.