How to Check For Partial Decidability

Question

What is Partial Decidability ?  How do we check whether a problem is Partialy Decidable or Not ?

Comments

Any specific question?? So that I can make clear the point ..

---

Yes @Habibkhan SIR ,  Here  it is : https://gateoverflow.in/725/gate2001-2-7   I didn't understand How it is partial discidability is beeing checked for 

Answer 1

Actually the problem mentioned there is known as state entry problem and is a standard RE but not REC or u can say semidecidable or partially decidable problem..I m listing below a few problems which u should know which are semidecidable problems..

A) Halting Problem :

Given a Turing Machine and an input string whether it will halt on that string or not..

B) Blank Tape Halting Problem :

The blank tape problem takes a machine and an empty tape and tells if this machine halts or not..

C) State Entry Problem :

 The problem is to determine whether Turing machine TM  , when given input w, ever enters state q.

D) Post Correspondence Problem :

https://en.wikipedia.org/wiki/Post_correspondence_problem

E) Modified Post Correspondence Problem :

http://www.iith.ac.in/~subruk/4510/pcp.pdf

The problems D) and E) however become decidable(recursive) if we consider unary alphabet..

Comments

See anything which is not decidable is referred to as undecidable..But it is a general class as contains some problems belonging in RE domain which accept string which belongs to such languages but may hang forever in the case of rejection..

But for non RE languages even we do not know whether a machine will halt on acceptance also..

So both cases are actually undecidable..However to be more precise the first one is semidecidable as it at least halts on members of language..

So in a nutshell I would like to say for RE languages(or RE sets) they are also known as semidecidable and NOT RE sets (or languages) are not even semidecidable..However both are referred as undecidable in general..

---

@Habib. In blank tape halting problem, does the input tape current cell is BLANK or the entire tape is BLANK ?

---

Blank Tape means Nothing is given in input all blanks.