Church-Turings tese, (efter Alan M. Turing og Alonzo Church), tese fra 1936, der udtrykker den forbavsende erfaring, at alle modeller til afgrænsning af beregnelige funktioner (se beregnelighed) har ledt til samme resultat. Tesen har stor betydning inden for datalogi.
Studiet af beregnelige funktioner kræver en eksakt model af eller notation for beregning, og hertil kan bland andet Turingmaskinen og lambdakalkylen bruges. Tesen udsiger, at klassen af funktioner, hvis værdier kan beregnes trinvis ud fra veldefinerede regler, netop er dem, der kan beregnes af en Turingmaskine eller ækvivalent i lambdakalkylen. Church-Turings tese kan ikke bevises formelt pga. den intuitivt forståelige, men upræcise formulering "trinvis ud fra veldefinerede regler".
Church-Turings tese indebærer, at der ikke kan bygges fysiske maskiner, der kan beregne flere funktioner, end de funktioner, der kan beregnes af en Turingmaskine.
Man arbejder dog i teoretisk datalogi med hypotetiske maskiner, der er Turingmaskiner udstyret med orakler, der kan beregne visse veldefinerede klasser af funktioner, der ikke kan beregnes med en almindelig Turingmaskine. Disse hypotetiske maskiner kan beregne mere end Turingmaskiner, men uanset oraklet vil der stadig være funktioner, der ikke kan beregnes af disse hypotetiske maskiner.
Kommentarer
Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.
Du skal være logget ind for at kommentere.