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

undecidable and not recursively enumerable

decidable and recursively enumerable

undecidable but recursively enumerable

decidable but not recursively enumerable

Let be the encoding of a Turing machine as a string over ∑= {0, 1}.

1.	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
Answer» C. undecidable and not recursively enumerable

Discussion

No Comment Found

Related MCQs

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in 1 millisecond is ____________
SQL allows tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below: select * from R where a in (select S.a from S)
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements: S1: There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset. Which one of the following is CORRECT?
The number of distinct positive integral factors of 2014 is _________________________
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .
The product of the non-zero eigenvalues of the matrix 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 is ______
In the Newton-Raphson method, an initial guess of x0 = 2 is made and the sequence x0, x1, x2 … is obtained for the function 0.75x3 – 2x2 – 2x + 4 = 0 Consider the statements (I) x3 = 0. (II) The method converges to a solution in a finite number of iterations. Which of the following is TRUE?
The value of a float type variable is represented using the single-precision 32-bit floating point format IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mantissa. A float type variable X is assigned the decimal value of −14.25. The representation of X in hexadecimal notation is
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

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

Discussion

No Comment Found

Related MCQs

Reply to Comment