0 votes 0 votes What is semi and Partially decidable...and how we know Theory of Computation decidability + – bhavnakumrawat5 asked Oct 1, 2018 bhavnakumrawat5 664 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Semi decidable languages are those for which there exists a Turing machine which halts if a string belongs to the language(YES cases) and may or may not halt for strings which does not belong to the language (No cases). Shobhit Joshi answered Oct 1, 2018 Shobhit Joshi comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments srestha commented Oct 1, 2018 reply Follow Share undecidable is not decidable, which is either partially decidable or not partially decidable 1 votes 1 votes Mk Utkarsh commented Oct 1, 2018 reply Follow Share We say halting of TM is undecidable, yes it is because problems which are undecidable can be partially decidable. So all partially decidable problems are undecidable but converse is not true. 0 votes 0 votes garimanand commented Oct 13, 2018 reply Follow Share Partially decidable means recursively enumerable languages which can halt for yes but may or may not halt for No and unrecognizable are languages that are not recursively enumerable languages and according to rice theorem if they have TM yes and TM no and TM yes is a proper set of TM no . then it is completely undecidable which is not even partially decidable. so in short undecidable languages having TM halts for YES and may or may not halt for NO is partially decidable.and languages for which are unrecognizable by TM are undecidable but not Partially decidable 0 votes 0 votes Please log in or register to add a comment.