Turingovská úplnost: Porovnání verzí

'''Turing-kompletní''', '''turing-úplný''' nebo '''turing-ekvivalentní''' ({{Vjazyce2|en|'''Turing-complete'''}}) je stroj ([[počítač]]), [[programovací jazyk]], úloha nebo [[abstraktní stroj]], který má stejnou výpočetní sílu jako [[Turingův stroj]]. Tato třída je důležitá proto, že není znám žádný způsob řešení úlohy, která je těžší (podle [[Church-Turingova teze|Churchovy hypotézy]] žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turing-kompletní stroj je tak [[univerzální]], jak je jen možné (to ovšem neříká nic o [[efektivita|efektivitě]]). Speciálně lze sestrojit [[Turingův stroj#Univerzální TS|univerzální Turingův stroj]], který dokáže simulovat libovolný jiný turingův stroj (zadaný na vstupu).