= Solution
For example, take
$$
\boxed{\mathcal L=\{\operatorname{enc}(M):M\text{ has an even number of states}\}.}
$$
This is a <decidable language>: check that the <input> is a valid <Turing machine encoding>, count its declared states, and test the count's <integer parity>. There are <Turing machines> with even state counts and <Turing machines> with odd state counts, so the <formal language> contains some but not all valid descriptions.
\b[There is no contradiction with <Rice's theorem> because this is a syntactic property of the description.] Add one unreachable state to a <Turing machine>, assigning any permitted transitions to it. The accepted <formal language> is unchanged, while the <integer parity> of the state count changes. Thus the property is not an <extensional property of programs>, which is an essential hypothesis of <Rice's theorem>.
Back to article page
