Register

Some basic properties

812 views
0 0 votes
1.   Turing Decidable means Recursive language

2.   Turing recognizable means REL

3.   Decidable means Recursive

4.   Undecidable means REL or Turing Recognizable.

 

Does the 4th statement is correct or not . Plz give valid assertions and reasons.

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · Closure propertiesNext → · doubt in finding coe...
← Previous in category · Closure propertiesNext in category → · Reducability
Position:
Show:

Related questions

0 0 votes
2 answers 2 answers
1.4k
1.4k views
abhinowKatore asked Oct 18, 2022
1,406 views
ACE 2023 Test series: TOC: Basic properties
0 0 votes
1 1 answer
90
90 views
GO Classes asked Sep 21
90 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $X$ and $Y$ be regular languages. Their symmetric difference is$$X\triangle Y=\{w:w\text{ belongs to exactly one of }X,Y\}$$. Which expression correctly represents $X...
2 2 votes
1 1 answer
132
132 views
GO Classes asked Sep 19
132 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...
1 1 vote
1 1 answer
93
93 views
GO Classes asked Sep 19
93 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ be regular where specified. Which of the following languages are guaranteed to be regular?$\{ww\mid w\in{0,1}^*\}$ $\{ww\mid w\in L_1\}$ $\{w\mid ww\in L_1\}$ $...