The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
656 views

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.

  1. Show that $X$ is undecidable
  2. Show that $X$ is not even partially decidable
asked in Theory of Computation by Veteran (68.8k points)
edited by | 656 views
sir halting problem is undecidable but semi deciadable. i.e recursive enumerable. and the given problem is complement of halting problem. and we know recursive enumerable is not closed under complementation. then how can we say that the answer is not even semi decidablde

1 Answer

+18 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.

answered by Veteran (332k points)
selected by
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 !!!

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)

 

thanks !!!
Sir there partially decidable is same as undecidable
No. Some undecidable problems are partially decidable- example halting problem. All decidable problems are also partially decidable. Partially decidable set is a superset of decidable which also includes some undecidable problems- for which we have solution for "yes" instances at least.

Hi @GO Seniors,

X: Given a Turing machine M over Σ and any word w∈Σ, does M loop forever on w?

Here also we have two cases --> 

if $ w\in \sum$ then answer of  $X$ is NO. But

if  $ w\notin \sum$ then we can not say anything. 

then, Why is it not considered in partially decidable class ? 

 

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,544 questions
39,231 answers
109,311 comments
36,613 users