Turingin täydellisyys tarkoittaa sitä, että ohjelmointikieli pystyy suorittamaan Turingin koneen toiminnot. Tämä on käsite hyvin yksinkertaiselle mekaaniselle tietokoneelle, jota joskus kutsutaan yksinkertaisimmaksi koneeksi, jota voidaan pitää tietokoneena. Lähes kaikilla nykyään käytetyillä ohjelmointikielillä ja teoriassa niitä käyttävillä tietokoneilla on Turingin täydellisyys.
Turingin täydellisyyden käsite on peräisin brittiläiseltä tietojenkäsittelytieteilijältä Alan Turingilta, jonka työ käsitti koodatun viestin tulkinnan toisen maailmansodan aikana. Hänen työnsä laskennassa oli sellaisen filosofian kehittäminen, mitä tietokone todella voisi tehdä. Tähän sisältyi käsite, että tietokoneet toimivat yksinkertaisesti suorittamalla algoritmeja. Tämä tarkoittaa, että he noudattavat kiinteitä sääntöjä tietojen käsittelyyn ja ongelmien ratkaisemiseen. Tämä tarkoittaa, että tietokone ei “ajattele” tai tee päätöksiä kuten henkilö voi.
Konseptin havainnollistamiseksi Turing kuvasi hypoteettista konetta, jota hän kutsui “a-koneeksi”, ja “a” tarkoitti automaattista; toiset kutsuivat sitä myöhemmin Turingin koneeksi. Kone käsittelee nauhakelaa, joka voi liikkua taakse- tai eteenpäin ja sisältää symbolirivin. Kone voi milloin tahansa käsitellä yhden symbolin ja tarvittaessa muuttaa sitä. Käsitettä varten nauhakela voi olla äärettömän pitkä, mikä tarkoittaa, että tietokoneen muisti ei ole luonnostaan rajoitettu. Tämä on analogia ajatukselle, että kun tietokoneella on joukko ohjeita, joita on noudatettava, tietomäärä, johon se voi soveltaa näitä ohjeita, on vain fyysisten rajojen alainen.
Ironista kyllä, useimmissa tietokoneissa ei nykyään ole Turingin täydellisyyttä. Tämä johtuu siitä, että niillä on rajoituksia käytettävissä olevalle tallennustilalle ja siten käsiteltäville tiedoille. Niillä on myös fyysisiä rajoituksia, varsinkin kun ne lopulta kuluvat. Se on itse asiassa ohjelmointikieli, jolla on Turingin täydellisyys. Tämän vuoksi tietokone, jossa on tällainen ohjelma, ei ole Turingin tietokone, mutta sitä voidaan simuloida.
Turingin täydellisyyttä ei pidä sekoittaa Turingin testiin. Tämä oli Turingin suunnittelema kokeilu nähdäkseen, osaavatko tietokoneet keskustella luonnollisella kielellä. Testin periaate on, että jos ihminen ei pysty erottamaan vain tekstiviestejä käyttävän keskustelun tietokoneen ja toisen ihmisen välillä, tietokone läpäisee testin. Jotkut tietokoneet ovat läpäisseet testin, kun keskustelun aihealue on rajoitettu, mutta kukaan ei ole tehnyt sitä rajoittamattomassa keskustelussa.