The Gateway to Computer Science Excellence

+20 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

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

+2

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

+22

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)

+11

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.

0

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 ?

+1

Here for this problem, we can say 'No' for all the 'No' instances. But can't say 'Yes' for 'yes' instances. Hence undecidable

0

Does w loop forever on M??

Ans >Yes or No

When Yes Undecidable.But when No halt so its is partial decidable.

plz any one rectify me what is wrong with this?

Ans >Yes or No

When Yes Undecidable.But when No halt so its is partial decidable.

plz any one rectify me what is wrong with this?

0

@chhotu partially decidable means we can say yes for all yes instances but cannot say no for "no" instance. This problem is complement of "Halting problem of Turing machine" in which we cannot even say "yes" for all yes instances.

0

Given a Turing machine MM over ΣΣ and any word w∈Σw∈Σ, does MM loop forever on w

If you answer "yes" or "no" for looping question indirectly you are answering looping problem of TM which is undecidable.

Summarizing it: Decidable - we can say yes or no for both instance- recursive

partially decidable - we can say yes only for "yes" instance. REL.

Totally undecidable : cannot say yes for **every** yes case. Not even REL.

+5 votes

Partially decidable is same as semi-decidable language which means that there exists a Turing Machine for such languages(given an input, the machine can accept/reject/loop) but we are not sure whether there is any Total Turing Machine(given an input, the machine can accept or reject but does not loop) or not.

Ref: https://www.youtube.com/watch?v=v2VuM0AIZVU&t=13s **<2:47 to 4:30>**

Here the question is whether M loops on a given string 'w' which is same as saying whether M does not halt on w. As Arjun Sir said, this is just the complement of Halting problem.

Halting problem is an undecidable problem. Given an input x to a machine M, there is no way to decide whether M will halt(accept or reject) or not(loop). The language L={M#x | M halts on x} is **R.E but not Recursive. **

So** complement of Halting problem** would be **complement of language which is (R.E. but not Recursive)** which is **Non-R.E.**

Why is it so? Ref: https://www.youtube.com/watch?v=VqDMudEzZCo **<0:00-7:00>**

Non R.E. means unrecognizable meaning there does not exist any Turing machine also for such languages hence they are not even partially decidable.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,516 answers

195,580 comments

101,143 users