Turing complete

De Wikipedia, le encyclopedia libere
Saltar a: navigation, cercar

In le theoria de computatores e fictive e real, de linguages de programmation, e de altere systemas logic, un systema de Turing complete es un systema que ha un poter computational equivalente a un machina de Turing universal. Le concepto es nominate in honor de Alan Turing.

In altere parolas, le systema e le machina universal de Turing pote emular le un le altere. Nulle computator satisface iste requirimento completemente, proque un machina de Turing ha un capacitate de immagazination illimitate, impossibile a emular in un apparato real. Con iste exception, totevia, tote le computatores moderne es systemas de Turing complete, como es tote le linguages de programmation pro uso general.

Le completessa de un systema de Turing es significative in que omne designo plausibile de un apparato computational inventate usque ora (mesmo computatores quantic) pote esser emulate per un machina de Turing universal. Assi, un machina que pote ager como un machina de Turing universal pote, in principio, exequer omne calculation del qual omne altere computator es capace. Nota, nonobstante, que isto dice nihil super le effortio requirite pro scriber un programma pro le machine, ni super le tempore requirite pro facer un tal calculation.

Vide le articulo super le theoria de computabilitate pro un longe lista de systemas de Turing complete, assi como plure systemas minus potente, e plure systemas theoric que es mesmo plus potente que un machina de Turing universal.

Vide etiam[modificar | modificar fonte]