Church-Turing Thesis Cannot Possibly Be True

The thesis asserts this: If an algorithm A computes a partial function f from natural numbers to natural numbers then f is partially recursive, i.e., the graph of f is recursively enumerable.

The thesis has been formulated in 1930s. The only algorithms at the time were sequential algorithms. Sequential algorithms were axiomatized in 2000. This axiomatization was used in 2008 to prove the thesis for sequential algorithms, i.e., for the case where A ranges over sequential algorithms.

These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc.

The question whether the thesis is true in full generality is actively discussed from 1960s. We argue that, in full generality, the thesis cannot possibly be true.

Opens in a new tab

Speaker Details

Professor Emeritus, Yuri Gurevich
Yuri Gurevich is Professor Emeritus at the University of Michigan, recently retired from MSR where he worked 20 years as a Principal Researcher. He is also a fellow of ACM, Guggenheim Foundation and EATCS, a foreign member of Academia Europaea, and Dr. Honoris Causa of a Belgian and a Russian university.

Opens in a new tab

Date:

September 21, 2018

Speakers:

Yuri Gurevich

Affiliation:

University of Michigan