2
$\begingroup$

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!

$\endgroup$

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ToneCat May 19 at 2:44
  • $\begingroup$ An input has several prefixes. How do you handle that? $\endgroup$ – Yuval Filmus May 19 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.