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.

Turingkomplette programmeringssprog

Et programmeringssprog siges at være Turingkomplet, hvis det kan simulere enhver Turingmaskine og dermed beregne alle de funktioner, som kan beregnes af Turingmaskiner. De fleste moderne programmeringssprog er Turingkomplette forudsat, at de har adgang til ubegrænset lagerplads. Netop ubegrænset lagerplads er en nødvendig (men ikke tilstrækkelig) forudsætning for Turingkomplethed.

Det er i reglen ikke svært at bevise, at et sprog er Turingkomplet: Man skal blot vise, hvordan en given Turingmakine kan oversættes til et program i sproget. Da Turingmaskiner er meget simple, er det i de fleste tilfælde (men ikke altid) nemt. Under forudsætning af, at Church-Turings tese holder, er det ikke nødvendigt at lave beviser for det omvendte: At en Turingmaskine kan simulere programmeringsproget.

Læs mere i Den Store Danske

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.

eller registrer dig