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



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
.