search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.

Recent questions tagged ricestheorem

0 votes
1 answer 16 views
If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM
asked Jul 12 in Theory of Computation princeit07 5 points 16 views
0 votes
0 answers 16 views
What are the languages, RE or not RE? Please explain using Rice’s theorem or otherwise. 1) L={⟨M⟩|TM halts on empty string} 2) L={⟨M⟩|TM halts on empty string} 3) L={⟨M⟩|TM halts on no input} Not sure how rice’s theorem is working here.
asked Jul 30, 2020 in Theory of Computation pranavsettaluri9 5 points 16 views
0 votes
0 answers 28 views
Here in place of or if and was given then is it correct: $T_{yes}=\{a,b\} \ \ T_{no}=\{\ \Sigma^* \}$ Here for $T_{yes}$ x = a or b is in the language, but let y = ab is not in the langugage, in $T_{no}$ there is no x or y which ... since the language of $T_{no}$ is universal language also $T_{yes}$ is a proper subset of $T_{no}$ so the language is not RE. Please provide your valuable inputs.
asked Jan 31, 2020 in Theory of Computation shethnisarg 5 points 28 views
0 votes
0 answers 29 views
L1 = {<M> | M is a TM, M0 is a TM that halts on all inputs, and M0 ∈ L(M) } My understanding is as follows, We are given an encoding of a TM which accepts some set of strings, We need to figure out if that Language contains an encoding of another TM (M0) ... are any mistakes in my approach. (I didn't get the ans the first time I solved and it feels like I am trying to justify the given ans).
asked Jan 30, 2020 in Theory of Computation abhiram144 5 points 29 views
0 votes
1 answer 61 views
I am not able to understand Rice theorem. Can anyone suggest any reference where Rice theorem is explained properly with proper understandable explanation? Thank you
asked Nov 24, 2019 in Theory of Computation Pratyush Priyam Kuan 1.1k points 61 views
0 votes
1 answer 42 views
https://gateoverflow.in/1994/gate2014-2-35 in this question can’t we directly apply rices theorem we can have a Tyes for languages with 2014 length input and Tno for Σ* since Tyes subset Tno it shouldnt be recursively enumerable . could someone elaborate where i am wrong?
asked Aug 6, 2019 in Theory of Computation TUSHAR_BHATT 15 points 42 views
To see more, click for the full list of questions or popular tags.
...