Church-Turing thesis

The Church-Tur­ing the­sis (of­ten ab­bre­vi­ated CT the­sis) states:

Every effec­tively com­putable func­tion is Tur­ing-computable

That is, for ev­ery func­tion which can be com­puted by phys­i­cal means noteSo no hy­per­com­put­ers there ex­ists a Tur­ing ma­chine which com­putes ex­actly that.

The Church-Tur­ing the­sis is not a definite math­e­mat­i­cal state­ment, but an in­duc­tive state­ment which af­firms that ev­ery sen­si­ble model of com­pu­ta­tion we can come up with is equiv­a­lent or at least re­ducible to the model pro­posed by Tur­ing. Thus, we can­not prove it in a math­e­mat­i­cal sense, but we can gather ev­i­dence for it.

For ex­am­ple, this model was proven to co­in­cide with Church’s lambda calcu­lus, an­other uni­ver­sal model of com­pu­ta­tion, and the equiv­alence be­tween Church’s lambda calcu­lus and Tur­ing’s au­to­matic ma­chines is of­ten taken as ev­i­dence that they cor­rectly cap­ture our in­tu­ition of “effec­tively com­putable”.

There are many con­se­quences of the CT the­sis for com­puter sci­ence in gen­eral, ar­tifi­cial in­tel­li­gence, episte­mol­ogy, and other fields of knowl­edge.



  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.