edited by
1,578 views
3 votes
3 votes

Consider the following two decision problems

  1. Whether a Turing Machine takes more than 481 steps on input epsilon?
  2. Whether a Turing Machine accepts the null string epsilon?

Which of the following statements is true ?

  1. Problem a is decidable but b is not
  2. Problem a is undecidable but b is decidable
  3. Both a and b are decidable
  4. Both a and b are undecidable
edited by

2 Answers

1 votes
1 votes
Whether a Turing Machine takes more than 481 steps on input epsilon ?

If u will carefully think ,then it is saying that after finite (481 steps) steps .Then we are able run run turing machine exactly 481 times and says that whether it will take epsilon or not so it is decidable problem.

But Emptiness problem always Undecidable with respect to turing machine always remember.

Related questions

2 votes
2 votes
2 answers
2
rahul sharma 5 asked Aug 7, 2017
650 views
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?{⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M...
5 votes
5 votes
2 answers
3
Kapil asked Sep 27, 2016
2,028 views
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
1 votes
1 votes
1 answer
4
Abhipsa asked Jan 22, 2019
339 views
What is the difference between Turing Recognizable and Turing Decidable?Thanks!