NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
1

### GATE CSE 2001

MCQ (Single Correct Answer)
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum ,$$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,}$$ does the computation of $$M$$ on $$w$$ visit the state $$q''$$

Which of the following statements about $$X$$ is correct?

A
$$X$$ is decidable
B
$$X$$ is undecidable but partially decidable
C
$$X$$ is undecidable and not even partially decidable
D
$$X$$ is not a decision problem
2

### GATE CSE 1991

MCQ (Single Correct Answer)
Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ?$$
A
It could be un-decidable
B
It is Turing-machine recognizable
C
It is a regular language
D
It is a context-sensitive language
3

### GATE CSE 1990

MCQ (More than One Correct Answer)
It is decidable whether:
A
An arbitrary Turing machine halts after 10 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the product of two numbers.
D
None of the above.

## Explanation

Case (a):
Just run the TM for 10 steps and see it halts or not. So this is decideable.

Case (b):
The printing problem of TMs is Undecidable. This can be reduce to the halting problem when the TM halts let it print something.

Case (c):
Multiplication, Addition can be done by TM so this is decidable.
4

### GATE CSE 1989

MCQ (More than One Correct Answer)
Which of the following problems are un-decidable?
A
Membership problem in context - free languages.
B
Whether a given context - free language is regular.
C
Whether a finite state automation halts on all inputs.
D
Membership problem for type $$0$$ languages.
Write for Us

Do you want to write for us? Help us by contributing to our platform.

#### Questions Asked from Undecidability

On those following papers in Marks 2
Number in Brackets after Paper Indicates No. of Questions
GATE CSE 2020 (1)
GATE CSE 2015 Set 3 (1)
GATE CSE 2014 Set 3 (1)
GATE CSE 2013 (1)
GATE CSE 2005 (1)
GATE CSE 2001 (1)
GATE CSE 1991 (1)
GATE CSE 1990 (1)
GATE CSE 1989 (1)

### Joint Entrance Examination

JEE Main JEE Advanced WB JEE

### Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

NEET

Class 12