Turing kompleteco

El Vikipedio, la libera enciklopedio
Salti al navigilo Salti al serĉilo

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.