An Exercise in Unplugging the Church-Turing Thesis [Part 1]

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.

 

Errata (since January 2019)

  • 21 January 2019:
    1. Bottom of page 2: "then M can print one more output symbol ..." --> "then V can print one more output symbol ..."
    2. Page 8: Ignore the itemized statement "Knowledge of all (x,f(x)) pairs will still not suffice ...", for I have proved a stronger result in the paper. The same remark holds for the similar statement made on page 32.
  • 7 February 2019:
    1. I often write <M_d, w_d> instead of <M_d, w_e>. This type of error is easy to correct, e.g. in the proofs of Theorems 25 and 59, and in the proof on page 39.
  • 21 February 2019:
    1. In the proof of Th.25, I implicitly assume that strings 0, 00, and 01 represent unique naturals. The proof can be generalized so that this assumption need not be made.
    2. The second clause of Def.4 on p.12 needs to be: "f(x) = undefined otherwise". As a result, some proofs need minor changes.
    3. Most annoying is Def.17, which needs a drastic change. As a result, Lemma 21 needs to be weakened.

PDF: 

Tags: