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 nontrivial 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. Nontrivialness 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 LogicoPhilosophicus
.
 FollowUps:
 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):
Relevant Pages
