edited by
4,531 views
32 votes
32 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.

  1. Show that $X$ is undecidable
  2. Show that $X$ is not even partially decidable
edited by

3 Answers

Best answer
43 votes
43 votes
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.
edited by
9 votes
9 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.

0 votes
0 votes

Best answer is in the comments by @tusharp

 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.

Related questions

36 votes
36 votes
2 answers
2
Kathleen asked Sep 14, 2014
5,265 views
Construct DFA's for the following languages:$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has ...
29 votes
29 votes
3 answers
3
Kathleen asked Sep 14, 2014
15,790 views
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least$N^2$$2^N$$2N$$N!$