9
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ From all your comments, it seems to me that you don't really get what computability is. Check you the definition of computability; make sure you understand what a universal Turing machine is and how it works; make sure you understand the fine points of enumerations, in particular Gödel enumerations (with s-m-n property!). Rice's theorem is very simple once the basics are understood, but it has little implications ... whatever you are trying to do, is my gut feeling. $\endgroup$
    – Raphael
    Mar 3, 2015 at 7:35

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ That does make sense. Does this mean that Rice's theorem is not applicable to languages with non-computable semantics, or are languages with non-computable semantics a generally "forbidden" concept (in the sense that results from computability theory are generally not applicable to them)? $\endgroup$ Feb 28, 2015 at 16:46
  • 1
    $\begingroup$ Non-computable semantics is an expression I made up for intuition. Semantics is usually defined as a mapping from syntax (read Gödel number) to some domain of value (read computable function). My expression is a bit of an oxymoron because a Gödel numbering is supposed to be defined so that the associated functions can be computed. I was trying to give an intuition for what you were doing, which was actually a wrong thing to do. But you should refrain from using such a "concept". Yes: take it as a forbidden concept, for the reason you state. $\endgroup$
    – babou
    Feb 28, 2015 at 22:39
  • $\begingroup$ Maybe there is another misunderstanding on my part here, but if I consider the semantics to be a composition of two functions, the first mapping program -> gödel number and the second gödel number -> computable function as you described it, then the gödel numbering could easily follow it's definition, but the first mapping would be computable iff we have "computable semantics". It may still be a useless concept, but there is no problem defining it, or is there? $\endgroup$ Feb 28, 2015 at 23:36
  • $\begingroup$ I am not sure how to answer you. Your construction makes me uneasy. For me the syntax of the program in some language is the Gödel number. I just read the text as a big number in some numeration system where all my characters are considered digits. So I consider a single mapping. Conversely, if you give me an enumeration of function, I read the number as some kind of syntactic representation. I just try to avoid making a difference. Now, you can introduce (computable) intermediary bijective mappings from N to N, and it will not change things very much. $\endgroup$
    – babou
    Mar 1, 2015 at 0:17
  • $\begingroup$ "I just read the text as a big number in some numeration system where all my characters are considered digits" - So you take the program as a string as an input and you it into a number, where each program corresponds to exactly one number (= bijection). Also you state "some numeration scheme", so it does not really matter how exactly that encoding works, as long as it is computable, isn't it? Sorry for being so persisent, but I really want to get this. $\endgroup$ Mar 1, 2015 at 0:44
2
$\begingroup$

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 some sets of functions, that works; not for others. But a new programming language is a new numbering of some programs, and that is not what Rice's theorem talks about.

For the purpose of Rice's theorem, we consider only Gödel enumerations of all partial recursive functions, and then it only states something about index sets, that is sets of all indices in that enumeration of functions in the given set.

That does not cover all sets of indices; and that's good, because there certainly are plenty of decidable properties of programs. See also here.

$\endgroup$
2
  • 1
    $\begingroup$ "A new programming language is a new numbering of some programs." - if I consider a turing-complete language, doesn't that mean it numbers all computable functions? Anyways, I think my misunderstanding was that Gödel numberings would not have to be computable themselves. $\endgroup$ Feb 28, 2015 at 18:10
  • $\begingroup$ @Skrjiban Every proper programming language is a Gödel enumeration. (To be clear, Gödel numberings are partially computable by necessity.) $\endgroup$
    – Raphael
    Mar 3, 2015 at 7:30
2
$\begingroup$

Not every enumeration of programs is "acceptable", since not every enumeration would allow you to effectively compute the function associated with the program from the index of the program. In other words, you would not have universal machines (utm property). The second property that is usually required to "accept" the enumeration is the smn property: you need to be able to compute the index of program instances in a uniform and effective way.

It is possible to prove (Roger's equivalence theorem) that any pair of enumerations enjoying utm and smn are recursively isomorphic, that is to say that you have an effective way to translate programs beteween the two enumerations. This makes your theory enumeration-independent.

This is already enough to stress the relevance of utm and smn, the two basic theorems of the "abstract" approach to computability.

Roger's theorem is presented as an exercise (sic!) in his book Theory of Recursive functions and effective computability (exercise 2-10, pag 41). But the proof is not very hard, indeed.

$\endgroup$
1
$\begingroup$

I found this interesting paper by Udi Boker and Nachum Dershowitz which adresses the problem I had, among other things. In the introduction, they state that (emphasis mine)

What does one mean by saying that “$f$ is computable”? One most likely means that there is a Turing machine $M$, such that $M$ computes $f$, using some string representation of the domain $D$. But what are the allowed string representations? Obviously, allowing an arbitrary representation (any injection from $D$ to $\Sigma^*$) is problematic – it will make any decision function “computable”. For example, by permuting the domain of machine codes, the halting function can morph into the simple parity function [...]

and further

Another approach is to allow only “natural” or “effective” representations. However, in the context of defining computability, one is obliged to resort to a vague and undefined notion of “naturalness” or of “effectiveness”, thereby defeating the very purpose of characterizing computability.

which explains what babou referred to as "computable semantics". The paper also contains this quote from Michael Rescorla:

I will suggest that purported conceptual analyses involving Church’s thesis generate a subtle yet ineliminable circularity: they characterize the intuitive notion of computability by invoking the intuitive notion of computability [...] We endow the syntax with a primitive semantics. I submit that [...] we must demand that the semantic correlation between syntactic entities and non-syntactic entities itself be computable. But then the proposed analysis does not illuminate computability non-circularly.

So according to the authors, the common formal definition of a computable function relies on the informal intuition on what computability means, which explains what puzzled me about gödel numberings.

$\endgroup$
4
  • 1
    $\begingroup$ Isn't that close to what I explained in the last two comments I sent you. I did state that it is CT Thesis that provides the definition of computability, and is thus the founding stone of the rest, though unprovable. I was expecting you to reply to these comments. - - - - - - Another point is that I do not see how this can be an answer to your question. Your question was about an error in your reasoning, and you were not the person to find this error. $\endgroup$
    – babou
    Mar 2, 2015 at 22:59
  • $\begingroup$ I am sorry if I offended you, your comments were clearly helpful! I wanted to respond that the existence of a computable compiler from language $L'$ to $L$ should be equivalent to the existence of a computable interpreter for $L'$, which got me thinking about what a "computable" interpreter would be, which got me thinking about how a gödel numbering could be "computable", which led me to the above paper. If that was already what you meant, then I was apparently unable to see it. $\endgroup$ Mar 2, 2015 at 23:07
  • $\begingroup$ But you are right, it is what made it clearly understandable to me, but it does not answer the initial question. I will mark your answer as accepted instead. $\endgroup$ Mar 2, 2015 at 23:15
  • $\begingroup$ Well, you thanked both Raphael and myself. But the way to thank people here is to vote for them, or to accept their answer. Unless you come up with a much better answer to the original question, you are supposed to show appreciation to positive contributions,. At least that is my understanding. Personally I never downvote people as a protest to the many incompetent people who downvote carelessly. Science is dialog, not vote. Regarding the definition of computable, look at the comments I sent you. The very concept is awkward because defined by Church-Turing Thesis. Good luck. $\endgroup$
    – babou
    Mar 3, 2015 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.