6. Decidable or not? Yes/no with one sentence explanatiorn. Given a program P an

Question

6. Decidable or not? Yes/no with one sentence explanatiorn. Given a program P and an input X, determine whether either P does not halt on X, or it halts and produces 42 as a result. Given a program P and an input X, determine whether either P halts and produces 42 as a result in less than one million steps, OR P on X is still running after one million steps. Given two programs P and Q and an input X, determine whether either both P and Q halt on X or both do not halt on X. Given two programs P and Q and an input X, determine whether either both P and Q halt on X in less a. b. c. d. Wi e. f. g. h. i. Given a program P and two different inputs X and Y, determine whether P halts on both X and Y. Given a program ctt program P, is P syntactically correct? Given a decidable language L, is there more than one TM M that will decide L? Given a Turing-acceptable language L, is there more than one TM M that will accept L? Given a Turing machine L, will it accept at least one string of length less than 10?

Explanation / Answer

A. This is similar to halting problem which is undecidable hence it is also undecidable

B. This is decidable because we can count the steps and decide

C. This is undecidable as explained above

D. This is undecidable as 100^100 is very large and will take a large time to compute so it becomes similar to halting problem

E. This is also undecidable

F. Yes this is decidable as IDE do the same thing

G. There can be

H. Yes it is also possible

I. Not necessary always

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.