# 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!

A language is semi-decidable if there is a Turing machine that halts for all strings in the language, and doesn't halt for strings not in the language.

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$$.

You take it from here.

• Great! Thank you so much for your help. Ive constructed a Turing machine M'. If M' halts on the prefix of x and the prefix of x is not in A, then M' rejects. If M' halts on the prefix of x and the prefix of x IS in A, then simulate: M on x. 1) accept if M accepts x 2) reject if M rejects x. 3) else loop forever. Correct me if I'm wrong here. – ToneCat May 19 '19 at 2:44
• An input has several prefixes. How do you handle that? – Yuval Filmus May 19 '19 at 6:03