Theoretical Computer Science is Closed Minded?

The Theoretical Computer Science community is raging following an article by Wegner and Goldin. Here’s the gist of what the paper says:

The (Theoretical Computer Science) TCS model is inaccurate because (Turing Machines) TMs express only closed-box functional transformation of input to output.

The point is that you can’t model Microsoft Word using a Turing Machine, because, trivially, Microsoft Word interacts with the user.

I’ve read carefully the reactions of the TCS community, at least those who responded on Lance’s blog, and it did not convince me that this paper was wrong or misleading. Some say, “Go read the papers, it proves that yes, you can model everything with a Turing Machine.”, but that’s not an argument I can accept. Others say that Interactive Computational Models have been done before. Fine, but most research is about rehashing what has been done in the past, in slightly different ways.

Here are some reactions from the community:

  • “they have a grant: NSF CISE/CCF SGER grant, Persistent Turing Machines: Beyond the Turing Thesis, I give up!” (meaning: “how could people who question the foundation of theoretical computer science ever get a grant?”)
  • “I am also very surprised that UConn allows Goldin to teach theory of computation.” (meaning, “clearly, someone who is critical of a field, can’t teach it!”)
  • “Forget incorrect- read any of their articles, and you’ll see that they’re literally cranks.”

To be clear, I’m not defending Wegner and Goldin per se. I don’t know enough about this particular problem to really take sides. Nor do I care enough, really. Maybe Wegner and Goldin are spinning a particular shallow idea in the hopes of becoming famous. Maybe, in the process, they are misleading people. But what I can tell you is that calling them cranks, accusing them of not being aware of the related work, being outraged because they have received a research grant, and so on, tells me that the Theoretical Computer Science is a conservative and closed minded community.

Allow me to quote myself:

Next time you review a paper or a funding application which attempts something fresh, don’t dismiss it because “the paper ignores 20 years of research.” We need to ignore fashions more, and encourage novel ideas. Don’t reward people because they follow the trends. We are supposed to give people tenure so that they can take risks, say things others don’t want to hear.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

5 thoughts on “Theoretical Computer Science is Closed Minded?”

  1. > you are essentially saying that you don’t care about the technicalities of the debate, but there are some commenters making bad arguments, and therefore all of TCS is closed minded. This makes no sense.

    Please read my blog post again, I did not write “therefore all of TCS is closed minded”. I chose my words carefully. And I don’t see what the technicalities of the debate have to do with the tone and the style of the response. You can disagree with someone without going as far as putting into question their ability to teach and get research grants.

    Please feel free to look at my work, be critical of its fundations and assumptions, and I bet you that I will not put in questions your abilities even if I strongly disagree and 1200 other people strongly disagree. Expect me to argue, but I don’t see anything in the paper which appeared in CACM that should bring forth any insults.

    Also, it is a bit more than just “bad arguments”. If I tell you you are a crank, Suresh, I’m sure you won’t agree that it was merely a “bad argument”. Imagine yourself the author and revisit the comments and now imagine how you’d feel?

    What are those signs pointing to? They clearly point to a closed minded community. I’m sorry, but that’s how it comes across, objectively so! This is what it is telling me, and I stand by it. Whether these signs are telling the truth is another story though.

    This is exactly, very much exactly, the same behavior seen in theoretical physics and which explains why the entire community is doing string theory even though it quite clear that it should not be the sole path. “If you are not doing string theory, we won’t accept your paper, we won’t give you a grant and you will certainly not get a job.”

    To be fair, some people do try to balance it out:

    “””I just think that the “TCS response” would look better if it consisted of polite and signed comments.””” (Boaz Barak)

    Amen to that!!! It seems obvious that at least some members of the TCS did not think that this “response” reflects well on the community.

  2. Dude,
    read the comment section fully. you are cherry picking from the top section of the comments. there is a very detailed set of discussions going on about specific claims made in the paper.

    Secondly, if you “don’t know enough about this particular problem to really take sides.”, and “don’t care enough, really”, why on earth are you taking sides in a meta-discussion ?

    you are essentially saying that you don’t care about the technicalities of the debate, but there are some commenters making bad arguments, and therefore all of TCS is closed minded. This makes no sense.

  3. > I’m not sure why idiotic comments makes the whole community closed minded.

    It does not. I did not say this. I asked the question… again, I point you to the title of my blog post:

    “Theoretical Computer Science is Closed Minded?”

    See the punctuation at the end? It was no mistake on my part.

    It served my purposes though, to suggest the TCS might be such, so that I could tie it back with the theoretical physics community.

    If the TCS is, indeed, open minded, then we don’t have anything to worry about, do we?

    > It is the claim that interaction represents a new and non-trivial extension of TMs that people are complaining about.

    Yes. I was able to grasp this, but I have not received convincing arguments that their thesis is trivial. Or maybe they went over my head.

    The gist of the matter seems to be this statement:

    “””The “Choice Machines” from Turing’s paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin’s claim that Turing asserted his machines have limited power.”””

    According to the comments, it is not clear that Turing showed such a thing:

    “””Lance (and others) seem to be misusing footnote [8] of the Turing 1936 paper as a demonstration that any c-machine can be represented as a-machine. This is plainly wrong and misleading.”””

    But I really don’t want to start with the technical details.

  4. “tells me that the Theoretical Computer Science is a conservative and closed minded community.” sounds like a damning of the entire community to me.

    At any rate, here’s my beef, more succinctly.

    1. you jump on some of the early, admittedly rather distasteful, comments, while disregarding the majority of comments later on that involved a fairly technical, and passionate discussion of the merits of the argument.

    Any blog thread has its flames, and a TCS blog is no different. I’m not sure why idiotic comments makes the whole community closed minded.

    2. You assume that the substance of the objections to the Wegner-Goldin paper are the ones you outline. Yes, there were mentioned, but look at the discussion that ensued later on. There is a substantive argument to be made in rebuttal of the Wegner/Goldin thesis, and many are making it. What about that ?

    3. A bad argument is a bad argument. getting to the heart of the matter, I recommend that you read some of the papers on interactive TMs yourself. The idea of interactivity as a computational paradigm is perfectly reasonable, and in fact no one is complaining about that aspect of the work. It is the claim that interaction represents a new and non-trivial extension of TMs that people are complaining about.

  5. Daniel is a colleague with whom I often have some very deep discussions. But I am no computer scientist, solely a humble philosopher specialized in epistemology (philosophy of science or theory of knowledge, as you wish). I just read the article that started all this noise around openmindedness in a particular scientific community. (What I read in the above comments suggests that from a sociological point of view, this openmindedness problem is certainly an issue in the field; otherwise, well, people would not have reacted as to defend and support what Khun called in the late sixties a “normal science”. But so much so with this sociological remark.)The principal problem I have with the Wegner and Goldin article is that its thesis concerns an historically and supposedly well founded opposition between rationalism and empiricism, and that it puts all rationalists in the same bag, which is said to be about a priori reasoning, which is clearly incorrect; whereas empiricism is posed as superior to the latter because because of its supposedly more accurate account of what is “out there” in the observed world, which an evaluative or axiological judgement about a philosophical stance. Had the authors been more accurate themselves in their historical analysis, they could not not have noticed that this opposition was, from Kant onwards, largely forgotten. Kant, in effect, developped a theory of knowledge that is a fusion of rationalism and empiricism. This opposition was thereon solved; I do not mean to say uninteresting, but largely accepted. The authors could not, moreover, not noticed what in the last century (20th) philosophers and “hard science” and social sciences scientists had developped as theories of knowledge that incorporates both rationalists and empiricists moments. Sir Karl Popper comes to mind and, to be sure, he was a clear defensor of liberalism as the most democratic political and economical system: but he wasn’t an empiricist as our authors portrayed them to be. (In fact, they reproduced old humean thesis with no critical point of view; I suspect they haven’t read Hume for a very long time.) So, what is all this noise about? It is mostly about a philosophical thesis saying that empirical kwowledge is superior to rationalisation, because empiricists are supposed to be more aware of the changes that occurs in the world. But, I might ask, what is this world they are talking about? And what are the characteristics of this knowledge when it is only formalzed in an observational language, not in the language of the theory of models, let it be logical or mathematical? And how do they represent to themselves the role and the function of their past and actual knowledge they are putting in use in their observations of “the world”? What is the best method of observation? And last but not least: is observing a machine computing all it is capable to compute can be logically reduced to a so far unidentified type of empirical observation? If they offer a positive answer to this last question, they surely are no empiricists: for what they are observing is not the behavior of a material object in “the world”, but a series X of n-rules of computing. These are most surely no “natural” object, but a pure product of the human rational mind.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see