Turing complete

In le theoria de computatores e fictive e real, de linguages de programmation, e de altere systemas logic, un systema 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 immagazinage illimitate, impossibile de emular in un apparato real. Con iste exception, totevia, tote le computatores moderne es systemas Turing complete, como es tote le linguages de programmation pro uso general.

Le stato complete de un systema 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 machina, ni super le tempore requirite pro facer un tal calculation.

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

 Vide etiam 

 Alan Turing
 These de Church-Turing
 Machina de Turing
 Theoria algorithmic de information
 Libro A New Kind of Science per Stephen Wolfram
Categoria:Informatica theoric