Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) |x ∈ A*}. Which of the following statements is true:

f is computable if and only if Lf is recursively enumerable.

f is computable if and only if Lf is recursive.

If f is computable then Lf is recursive. But not conversely.

If f is computable then Lf is recursively enumerable, but not conversely.

Let A and B be finite alphabets and let # be a symbol outside both A a

1.	Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B. We say f is computable if there exists a Turing machine M which given an input x in A. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) \|x ∈ A*}. Which of the following statements is true:
A.	f is computable if and only if Lf is recursive.
B.	f is computable if and only if Lf is recursively enumerable.
C.	If f is computable then Lf is recursive. But not conversely.
D.	If f is computable then Lf is recursively enumerable, but not conversely.
Answer» B. f is computable if and only if Lf is recursively enumerable.

Discussion

No Comment Found

Related MCQs

Consider the following sets:S1. Set of all recursively enumerable languages over the alphabet {0,1}S2. Set of all syntactically valid C programsS3. Set of all languages over the alphabet {0,1}S4. Set of all non-regular languages over the alphabet {0,1}Which of the above sets are uncountable?
If L ϵ NP is a language such that L' ≤p L for some L' ϵ NPC, then:
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) |x ∈ A*}. Which of the following statements is true:
If \( L\) and \(\bar L\) are recursively enumerable, then L is
Consider the following languages.L1 = { | M takes at least 2016 steps on some input},L2 = { | M takes at least 2016 steps on all inputs} andL3 = { | M accepts ϵ},Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
Consider the following statements.I. The complement of every Turing decidable language is Turing decidableII. There exists some language which is in NP but is not Turing decidableIII. If L is a language in NP, L is Turing decidableWhich of the above statements is/are true?
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?I. if L4 ∈ P, then L2 ∈ PII. if L1 ∈ P or L3 ∈ P, then L2 ∈ PIII. L1 ∈ P, if and only if L3 ∈ PIV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P
Consider the following two statements about regular languages:S1: Every infinite regular language contains an undecidable language as a subset.S2: Every finite language is regular.Which one of the following choices is correct?
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language.Consider the following problems:(A) Is L(G1) = L(G2)?(B) Is L(G2) ≤ L(G1)?(C) Is L(G1) = R?Which of the problems are undecidable ?Choose the correct answer from the options given below:

Discussion

No Comment Found

Related MCQs

Reply to Comment