The Gateway to Computer Science Excellence
0 votes

Example# 3 from Part-1 Rice's Theorem from states as follows

(3) L(M) is recognized by a TM having even number of states

Sol: This is a trivial property. This set equals the set of recursively enumerable languages.

According to the previous examples, if i can find a Turing Machine which says Yes and a Turing Machine which says No, so i'll choose TNO as PHI (Empty String) and TYES as  a TM which accepts even number of states, then is it true that my L(M) is undecidable as the property is non-trivial, is my Reasoning correct ?

It seems like i can find TYES and TNO for every property then?
Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?

in Theory of Computation by Active (1.1k points) | 190 views

Yes or no means ...NO should reject  everything except even number of states

And the statement says it recognises which means for yes we can find a solution..but for NO it may either reject or never halt and enter loop

and that is turing machine recognisable

When YES and NO both are clear then it is TM decidable

How can we apply rice theorem in this example ?.. i think "TM having even number of states" is TM property , not a language property.


Please log in or register to answer this question.

Related questions

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
50,741 questions
57,252 answers
104,696 users