Which of the following is complement of a?
| A. | Recursive language is recursive |
| B. | Recursively enumerable language is recursively enumerable |
| C. | Recursive language is either recursive or recursively enumerable |
| D. | None of these |
|
Option: C Explanation : Click on Discuss to view users comments. |
If nL can be recognized by a multitape TM with time complexity f, then L can be recognized by a one-tape machine with time complexity DSD
| A. | O( f 2) |
| B. | o( f 2) |
| C. | o(h) |
| D. | O(h2) |
|
Option: A Explanation : Click on Discuss to view users comments. Suindu De said: (2:57am on Saturday 20th January 2018)
n is a multiplier to that language so if f is the compleexity then f should nbe the complexity.
|
If T is a TM recognizing L, and T reads every symbol in the input string, τT(n) ≥ 2n + 2, then any language that can be accepted by a TM T with τT(n) = 2n + 2 is
| A. | regular |
| B. | not regular |
| C. | uncertain |
| D. | none of these |
|
Option: C Explanation : Click on Discuss to view users comments. |
Consider an alternate Turing machine model, in which there is an input tape on which the tape head can move in both directions but cannot write, and one or more work tapes, one of which serves as an output tape. For a function f, denoted by DSpace ( f ) , the set of languages that can be recognized by a Turning machine of this type which uses no more than f(n) squares on any work tape for any input string of length n. The only restriction we need to make on f is that f(n) > 0 for every n. The language of balanced strings of parentheses are in
| A. | DSpace (1+ ⌈log2 (n + 1 ⌉). (⌈ x ⌉) means the smallest integer greater than or equal to x. |
| B. | DSpace (1+ ⌈log2 n⌉) |
| C. | DSpace ( 1+ ⌈ log2 n2⌉) |
| D. | none of these |
|
Option: A Explanation : Click on Discuss to view users comments. |
Which of the following problems is solvable ?
| A. | Writing a universal Turing machine |
| B. | Determining of an arbitrary turing machine is an universal turing machine |
| C. | Determining of a universal turing machine can be written for fewer than k instructions for some k |
| D. | Determining of a universal turing machine and some input will halt |
|
Option: A Explanation : Click on Discuss to view users comments. |
Syllabus covered in this section is-
This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like
Who can benefit
Various Search Terms Used For This Section Are
