Question

Which of the following problems is decidable?
a. whether a turing machine ever leaves a particular cell it it scanning
b.whether a turing machine started on blank tape will ever halt
c. whether a turing machine accepts at least two strings
d. whether a turing machine accepts a finite set

Answer 1

Answer on Question#38656 - Math - Other

Which of the following problems is decidable?

a. whether a turing machine ever leaves a particular cell it it scanning

b. whether a turing machine started on blank tape will ever halt

c. whether a turing machine accepts at least two strings

d. whether a turing machine accepts a finite set

Solution. a,b,c) These problems isn't decidable because of there are insufficient conditions or situation is incorrect.

d) If a turing machine accepts a finite set, it will halt and problem is decidable.

Answer: d)