An Exercise in Unplugging the Church-Turing Thesis

The year 2018 has been very productive: the attached pdf file contains my latest research findings, which pertain to the Church-Turing Thesis. The paper is under peer review. Its abstract follows.

Abstract

Resorting solely to concepts from classical computability theory, I provide mathematical arguments to doubt — if not dismiss, on an objective basis — the Church-Turing Thesis. Defending the thesis amounts to believing that "any process which could naturally be called an effective procedure can be realized by a Turing machine'' (Minsky, 1967). Specifically, I present a natural modification of the "Turing machine'' model of computation, called the "Alternative Deterministic Machine'' model (or ADM for short). The relevance of this new model hinges on the following observation: Turing machines have a lower model fidelity than ADM's with regard to human (and electronic) computers. Both a Turing machine and an ADM model a human computer who contributes to her research community by publishing mathematical findings. But, in reality, humans publish in a piecemeal fashion, rather than all in one go. Turing machines, as formally defined by Hopcroft & Ullman (1979), do not capture this particular trait of human activity, while ADM's do. To recapitulate in technical terms: a Turing machine provides meaningful output (for the outside world to see) instantly, after having halted, while an ADM provides meaningful output (to its environment) incrementally, before possibly halting. This distinction will allow me to (i) prove that Turing machines partially compute less functions on the naturals than ADM's, and (ii) prescribe an ADM-based method to generate a subset of the naturals that is not computably enumerable. I shall furthermore discuss multiple ways to generalize the ADM model. This discussion will lead to a new incentive, based on a mathematician-as-typewriter metaphor, to embrace even more powerful models of computation — i.e., the so-called "eventually correct machines'' in the literature — as natural formalizations of algorithms.

PDF: 

Tags: