Rice theorem and trivial properties for decidability proof

Question

I'm going to have a complexity theory exam and i understood the importance of Rice theorem in proving if given a language $L_{p}=(L|L\space satisfies\space the \space property\space\space p)$, is decidable or less.

Briefly if $p$ is trivial then $L_{p}$ is decidable and if $p$ is non trivial then $L_{p}$ is undecidable.

In a lot of exercises you have to prove that $L_{p}$ is undecidable by simply determing if p is trivial or not, I know that this can be a really "border" example but what if i want to prove that $L_{p}$ is decidable assuming that i have a trivial property $p$?

I can't figure out some examples of trivial properties, so i'm asking this question, can you give me some examples?

Thank you :)

Answer 1

How strong the Rice theorem is becomes clear if we formulate it a bit more precisely.

Let $S$ be an arbitary class of computable functions from $\mathbb N$ to $\mathbb N$. Assume that there is at least one computable function in $S$ and at least one is not.

Then, we cannot decide whether a giving turing machine computes some computable function in $S$.

So we cannot decide whether a given turing machine computes , for example

• a total function (defined everywhere)
• a constant function
• the squares
• the primes
• a strictly increasing function

and many more. The only case where we can decide it is if either $S$ is empty or $S$ contains every computable function. Either case is as trivial as it can be.