Didn't understand anything 😞

The Gateway to Computer Science Excellence

0 votes

Last time I said as it was undecidable it is actually Semi Decidable. We can't really say. As the condition M1 <M2 so Semi Decidability is satisfied. Hence, M1 is reduciblie to M2 is recursive enumerable.

One way theorem satisfies these conditions of semi-decidability are:

1. P <--- P

2. NP <---- NP

3. Recursive Enumerable <---- Recursive enumerable

4. Recursive lang <--- Recursive Language

One way theorem satisfies these conditions of semi-decidability are:

1. P <--- P

2. NP <---- NP

3. Recursive Enumerable <---- Recursive enumerable

4. Recursive lang <--- Recursive Language

0

@Arjun Sir, is not this question is incomplete? as we have not given any description about machine M either it is decidable or undecidable

than how we can decide, in that case it should be not even RE.

not getting answer provided by@hina firdaus

+2

M1 and M2 are inputs or like parameters to a function. That is from the input you can know the description of the 2 Turing machines and based on this you have to say if first one can be reduced to second or not -- so question is perfectly fine. For some inputs this is easy to say yes or no as answer but question is if we can always say yes or no correctly for all inputs.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,169 answers

193,877 comments

94,301 users