Church-Turing-tesen
From Wikipedia, the free encyclopedia
Church-Turing-tesen er indenfor beregnelighedsteori en hypotese om computeres opførsel. Tesen påstår, at enhver mulig udregning kan udføres af en algoritme på en computer, givet at der er tilstrækkelig megen tid og lagerplads til rådighed. Tesen kan ikke bevises matematisk; den bliver nogle gange brugt som en definition.
Uformelt siger tesen, at vores opfattelse af "algoritme" kan præciseres, og derved kan algoritmer køres på computere. En computer kan i teorien køre enhver algoritme; hvilket vil sige, at alle almindelige computere er ækvivalente med hensyn til teoretisk beregningskraft (computational power), og det er derfor ikke muligt at konstruere en beregningsenhed, som er mere kraftfuld end den simpleste computer (Turingmaskinen). Det skal nævnes at formuleringen omkring kraft ser bort fra praktiske faktorer som hastighed og hukommelse; den tager højde for alt, som er teoretisk muligt, givet ubegrænset tid og hukommelse.
Tesen blev først fremført af Stephen Kleene i 1943, men opkaldt efter Alonzo Church og Alan Turing.