Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is A)decidable and recursively enumerable B)undecidable but recursively enumerable C)undecidable and not recursively enumerable D)decidable but not recursively enumerable

Question

Quizplus · Accepted Answer

L is undecidable because determining whether a Turing machine accepts a string of a specific length (in this case, 2014) is equivalent to solving the Halting Problem, which is known to be undecidable. However, L is recursively enumerable because we can enumerate all strings of length 2014 and simulate the Turing machine on each string to see if it accepts any of them. If it does, we can list the encoding of that Turing machine. This process does not halt for machines that do not accept any string of length 2014, which is why L is not decidable but is recursively enumerable.

Let Be the Encoding of a Turing Machine as a String