Dark Mode

3,438 views

29 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

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

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.

0

0

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