My paper on the Church-Turing thesis is available here. It is primarily intended for younger generations in computing, who have not built their careers around defending the thesis, and for computer scientists who are open to questioning their belief system. My refutation of a weak interpretation of the thesis goes back to 2018, with a post here and a follow-up here, when RBMs were still called ADMs.

It has now come to my attention that Doukas Kapantais has refuted the Church-Turing thesis in one or even two different ways. (My apologies, but I will need weeks/months before I can be more specific regarding my understanding of his work). Please have a look at his two publications, listed on his website.

"Where logic and observation are insufficient to determine scientific conclusions, there historians may look to social explanations to fill the gaps." -- Mary Hesse, 1980

Why has the adoption of these findings been so slow? The answer lies in sociology; see the above quote. Slow adoption is not uncommon across various disciplines, including particle theory. As Peter Woit points out on his blog: 

"From talking privately to physicists, it became clear that the field of particle theory had for quite a while become disturbingly tribal. There was a string theory tribe, seeing itself as embattled and fighting less intelligent other tribes for scarce resources. Those within the tribe wouldn’t say anything publicly critical of the theory, since that would not only hurt their own interests, but possibly get them kicked out of the tribe. Those outside the tribe also were very leery of saying anything, partly because they felt they lacked the expertise to do so, partly because they feared retribution from powerful figures in the string theory tribe."

Hopefully the situation in computer science is not as dire. I suspect that most researchers in the field simply lack the time or the motivation to critically examine the fundamental principles of their discipline. With that said, please have a look at my `boundary object' interpretation of `the Turing machine' in this talk.

Errata of my paper:

Section 2.1, first sentence: 

• OLD: "... which contain neither ..." 
• NEW: "... which, if designed well, contain neither ..."

Section 4 and before Section 4.1:

• OLD: "Recall that RBM V prints at most  ..."
• NEW: "Recall that, for well-formed input, RBM V prints at most ..."

[last update: 30 August 2024]