0 votes 0 votes What is semi and Partially decidable...and how we know Theory of Computation decidability + – bhavnakumrawat5 asked Oct 1, 2018 bhavnakumrawat5 650 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 Deepanshu commented Oct 1, 2018 reply Follow Share then what is undecidable ? 0 votes 0 votes goxul commented Oct 1, 2018 reply Follow Share @Deepanshu Undecidable languages are the ones for which you cannot build a TM. 1 votes 1 votes Shobhit Joshi commented Oct 1, 2018 reply Follow Share Undecidable : There is no Turing machine that will always give an answer as "yes" or "no" i.e. it may or may not halt for strings that belongs to the language 1 votes 1 votes Deepanshu commented Oct 1, 2018 reply Follow Share Shobhit Joshi i mean to say that difference between semi and undecidable acc. to your definition 0 votes 0 votes Shobhit Joshi commented Oct 1, 2018 reply Follow Share semi will always halt for strings that belongs to a language while undecidable may or may not halt for strings in the language and both may or may not halt for strings not belonging to the language. 2 votes 2 votes Deepanshu commented Oct 1, 2018 reply Follow Share thanks bro 0 votes 0 votes bhavnakumrawat5 commented Oct 1, 2018 reply Follow Share and what is partial decidable..? 0 votes 0 votes 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.
