THE LOGIC IN COMPUTER SCIENCE COLUMN1 by

Quisani: Hello. It’s that time of the year again when we have a discussion, isn’t it? Author: Come on in. It is a busy time but I am happy to see you. Q: I am afraid my mood is rather critical today. A: That is all right. Speak your mind. Q: It is about computability and decidability. It seems to me that logicians’ computability has little to do with real computability. Some so-called computable functions are not computable in any practical sense. It is ridiculous to call them computable. A: It is well known that some computable functions are not feasibly computable. Q: But in what sense are they computable? You, logicians, have hijacked the notion of computability. Computability should mean practical computability. A: Practical computability is too hard to define. Take a function f, say, from binary strings to binary strings which is not computable by any Turing machine, and define g(x) = 1 if |x | < 210000, f(x) otherwise. Is g practically computable? Q: It is obvious that g is not computable. It seems reasonable to argue that g is practically computable because it is so easily computable on practical instances