Church-Turing thesis: Evidence for the Church-Turing thesis

As the Church-Tur­ing the­sis is not a proper math­e­mat­i­cal sen­tence we can­not prove it. How­ever, we can col­lect to in­crease our con­fi­dence in its cor­rect­ness.

The in­duc­tive argument

Every com­pu­ta­tional model we have seen so far is re­ducible to Tur­ing’s model.

In­deed, the the­sis was origi­nally for­mu­lated in­de­pen­dently by Church and Tur­ing in refer­ence to two differ­ent com­pu­ta­tional mod­els (Tur­ing ma­chines and Lambda Calcu­lus re­spec­tively). When they were shown to be equiv­a­lent it was mas­sive ev­i­dence in fa­vor of both of them.

A non-ex­haus­tive list of mod­els which can be shown to be re­ducible to Tur­ing ma­chines are:

  • Lambda calculus

  • Quan­tum computation

  • Non-deterministicTuringmachines

  • Register machines

  • The set of re­cur­sive functions

Lack of counterexamples

Per­haps the strongest ar­gu­ment we have for the CT the­sis is that there is not a widely ac­cepted can­di­date to a coun­terex­am­ple of the the­sis. This is un­like the strong church tur­ing the­sis, where quan­tum com­pu­ta­tion stands as a likely coun­terex­am­ple.

One may won­der whether the com­pu­ta­tional mod­els which use a source of ran­dom­ness (such as quan­tum com­pu­ta­tion or prob­a­bil­is­tic tur­ing ma­chines) are a proper coun­terex­am­ple to the the­sis: af­ter all, Tur­ing ma­chines are fully de­ter­minis­tic, so they can­not simu­late ran­dom­ness.

To prop­erly ex­plain this is­sue we have to re­call what it means for a quan­tum com­puter or a prob­a­bil­is­tic Tur­ing ma­chine to com­pute some­thing: we say that such a de­vice com­putes a func­tion \(f\) if for ev­ery in­put \(x\) the prob­a­bil­ity of the de­vice out­putting \(f(x)\) is greater or equal to some ar­bi­trary con­stant greater than \(1/2\). Thus we can com­pute \(f\) in a clas­si­cal ma­chine, for there ex­ists always the pos­si­bil­ity of simu­lat­ing ev­ery pos­si­ble out­come of the ran­dom­ness to de­ter­minis­ti­cally com­pute the prob­a­bil­ity dis­tri­bu­tion of the out­put, and out­put as a re­sult the pos­si­ble out­come with greater prob­a­bil­ity.

Thus, ran­dom­ness is re­ducible to Tur­ing ma­chines, and the CT the­sis holds.