Cheap and Secure Web Hosting Provider : See Now

[Solved]: Implications of Rice's theorem

, , No Comments
Problem Detail: 

Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong.

Lets take some non-trivial property of the set of computable functions, for example let $L = \{ f : \mathbb{N} \to \mathbb{N} \;|\; \text{f is a computable and total function} \}$. Obviously, $L$ is countably infinite and there's also a countably infinite number of computable functions not in $L$.

Now lets consider a turing complete programming language over of a finite set of instructions $\Sigma$ and the set of syntactically correct programs $P \subseteq \Sigma^*$, with $|P| = |\mathbb{N}|$. If I can choose the semantics of my language as I please, I may also number the programs as I please and so it should be possible to design a programming language where some subset of the programs computes exactly some arbitrary subset of the computable functions, as long as the cardinality matches. For example, let $P_{pal} = \{ w \in \Sigma^* \;|\; w\text{ is a palindrome} \}$, and each program $p \in P_{pal}$ compute a total function. Since $|P_{pal}| = |L|$, such a language should exist.

However, $isPalindrome(w)$ is obviously turing-computable and since $isPalindrome(w) \iff isTotal(w)$, we would thus have a program which decides the non-trivial property $L$, which is not possible according to Rice's theorem.

Where is the error in my deduction? Does this mean there is no programming language where each palindromic program (or rather of any computable structure) computes exactly the total functions (or rather any set of computable functions)? This really perplexes me.

Asked By : Skrjiban

Answered By : babou

What you forget is that all the mappings you use have to be computable. When you state that matching cardinalities ensure the existence of a mapping, that may be true, but the mapping is unlikely to be computable, precisely because that would let you get a contradiction with Rice theorem. In computability (at least for what I know of it), everything is either finite or countably infinite. So existence of mappings is usually not an issue. The problem is whether it is a computable one.

To say it differently, there is certainly a mapping (actually uncountably many) that associates precisely palindromic words with total computable functions. But, given such a palindrom $w$, which the mapping associates with a function $f_w$ there is no way you can actually use such a mapping to get the result of applying $f_w$ to some argument. You mapping does not give you any way of identifying the function or computing with it. Your language has non computable semantics.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback