patternMinor
Implications of Rice's theorem
Viewed 0 times
implicationsricetheorem
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#39906, answer score: 6
Revisions (0)
No revisions yet.