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
.



Relevant Pages

  • Re: How to use Rice Theorem to check if a function is undecidable or not?
    ... reverse of x}. ... How can we use Rice theorem to see ... 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 has the property or not. ... That is properties depending only on the inputs and outputs and not on the computation itself (ie, time complexity is an intensionnal property, not an extensionnal one). ...
    (comp.theory)
  • Re: how to remove but preserve tail.
    ... good idea to use a recursive function. ... to it or to reverse the tmp accumulated list. ... (defun remove-preserving-tail (item list) ... ((eql item (car sub)) ...
    (comp.lang.lisp)
  • Re: reverse not working: CL-USER> (rvrs (1 2 3)) (((NIL . 3) . 2) . 1)
    ... reucrsive function just as an exercise. ... Doing it with a simple recursive function, you will either need a lot ... temporary cons cells. ... Instead of taking the reverse of the rest, ...
    (comp.lang.lisp)