Turing kompleteco

Turing kompleteco estas esprimo uzita en komputebleca teorio por priskribi abstraktajn maŝinojn, kutime nomitajn aŭtomatojn. Tia aŭtomato estas Turing-kompleta, se ĝi povas esti uzata por emuli Turing-maŝinon. Ĝi ankaŭ nomiĝas komputile universala.

Plej multaj modernaj programlingvoj estas Turing-kompletaj. Estas lingvoj uzataj por klasifiki kaj priskribi la enhavon de dokumentoj; ekzemple HTML. HTML ne estas Turing-kompleta, ĉar ĝi ne povas aktive ŝanĝi la staton de la sistemo. HTML povas esti kombinata kun teknologio kiel JavaScript; ambaŭ kune fariĝas Turing-kompletaj. La normaj regulaj esprimoj, kiujn plej multaj programlingvoj uzas, ankaŭ ne estas Turing-kompletaj. Plej multaj regulaj esprimaj motoroj estis adaptitaj por inkluzivi malantaŭajn referencojn. La problemo pri tio estas, ke finia aŭtomato ne povas trakti malantaŭajn referencojn.