# Re: How to use Rice Theorem to check if a function is undecidable or not?

*From*: Aatu Koskensilta <aatu.koskensilta@xxxxxxxxx>*Date*: Sun, 05 Mar 2006 19:03:05 +0200

vmvictorvm@xxxxxxxxx wrote:

For example, lets say we have {P: for all input string x, P outputs the

reverse of x}. This is undecidable. How can we use Rice theorem to see

that this is undecidable?

Rice's theorem says that any non-trivial property of recursive functions is undecidable in the sense that there is no recursive function when given an index of a recursive function will tell whether or not it (or, rather, the recursive function it's an index of) has the property or not. Non-trivialness means that there is a function having the property as well as a function lacking it. Now, it is certainly the case that some recursive functions reverse their arguments while some do not and thus by Rice's theorem {P: P is the index of a function f, s.t. f(x) = x reversed} is undecidable.

As usual, one can formulate the above using Turing machines or any other model of computation instead of recursive functions.

--

Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

.

**Follow-Ups**:

**References**:

- Prev by Date:
**Re: Search for PhD Thesis: Arthanari, On Some Problems of Sequencing Grouping** - Next by Date:
**Re: How to use Rice Theorem to check if a function is undecidable or not?** - Previous by thread:
**How to use Rice Theorem to check if a function is undecidable or not?** - Next by thread:
**Re: How to use Rice Theorem to check if a function is undecidable or not?** - Index(es):