The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

Let a decision problem $X$ be defined as follows:

$X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$?

You may assume that the halting problem of Turing machine is undecidable but partially decidable.

- Show that $X$ is undecidable
- Show that $X$ is not even partially decidable

+20 votes

Best answer

The question asks if $M$ loop forever on $w$. If $M$ loop forever on $w, M$ wouldn't halt on $w$. And if $M$ doesn't halt on $w, M$ should loop forever. So, this problem is exactly same as asking if "$M$ doesn't halt on $w$", which is the complement of halting problem and is not even partially decidable. So, $X$ is not even partially decidable.

0

Can you please explain the second part in more detail. What does it actually mean to be partially decidable? Can you just elaborate a little ? thanks !!!

+15

Consider a decision problem. A decision can be either "yes" or "no". So. we can divide the problem cases to 2 parts- one where the answer is "yes", and one where the answer is "no".

Now, if the "yes" instance of the problem is given, suppose we (our TM) can always say "yes", then the problem is partially decidable (its language is recursively enumerable).

If we can also say "no" for all "no" instances of the problem, then the problem is decidable (its language is recursive).

NB: TM for a partially decidable but not decidable problem, will go to an infinite loop for **SOME** "no" instances. For some "no" instances it may say "no". (Obviously, it won't say "yes" for any no" instance)

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,943 questions

41,957 answers

119,194 comments

41,472 users