Kelengkapan Turing adalah ketika sebuah bahasa pemrograman mampu menjalankan fungsi dari sebuah mesin Turing. Ini adalah konsep untuk komputer mekanis yang sangat mendasar, kadang-kadang digambarkan sebagai mesin paling sederhana yang dapat dianggap sebagai komputer. Hampir semua bahasa pemrograman yang digunakan saat ini, dan secara teori, komputer yang menjalankannya, memiliki kelengkapan Turing.
Konsep kelengkapan Turing berasal dari Alan Turing, seorang ilmuwan komputer Inggris yang karyanya mencakup penguraian pesan berkode selama Perang Dunia II. Di antara karyanya tentang komputasi adalah pengembangan filosofi tentang apa yang sebenarnya bisa dilakukan komputer. Ini termasuk konsep bahwa komputer bekerja hanya dengan menjalankan algoritma. Artinya, mereka mengikuti seperangkat aturan tetap untuk memproses data dan pada gilirannya memecahkan masalah. Ini berarti komputer tidak “berpikir” atau membuat keputusan seperti yang bisa dilakukan seseorang.
Untuk mengilustrasikan konsep tersebut, Turing menggambarkan mesin hipotetis yang dia sebut “mesin”, dengan “a” berarti otomatis; yang lain kemudian menyebutnya mesin Turing. Mesin akan memproses gulungan pita yang bisa bergerak mundur atau maju dan berisi garis simbol. Setiap saat mesin dapat memproses satu simbol dan, jika perlu, mengubahnya. Untuk tujuan konsep tersebut, gulungan pita bisa sangat panjang, artinya memori komputer tidak terbatas secara inheren. Ini adalah analogi untuk gagasan bahwa begitu komputer memiliki serangkaian instruksi untuk diikuti, jumlah data yang dapat diterapkan oleh instruksi tersebut hanya tunduk pada batasan fisik.
Ironisnya, kebanyakan komputer saat ini sebenarnya tidak memiliki kelengkapan Turing. Ini karena mereka memiliki keterbatasan pada ruang penyimpanan yang tersedia dan dengan demikian data yang dapat mereka proses. Mereka juga memiliki keterbatasan fisik, terutama yang pada akhirnya mereka akan aus. Ini sebenarnya bahasa pemrograman yang memiliki kelengkapan Turing. Karena itu, komputer yang menjalankan program semacam itu bukanlah komputer Turing, tetapi dapat digunakan untuk mensimulasikannya.
Kelengkapan Turing tidak harus bingung dengan tes Turing. Ini adalah eksperimen yang dirancang oleh Turing untuk melihat apakah komputer dapat berkomunikasi dalam bahasa alami. Prinsip tes ini adalah jika manusia tidak dapat membedakan antara percakapan teks saja dengan komputer dan manusia lain, komputer lolos tes. Sementara beberapa komputer telah lulus ujian ketika jangkauan subjek percakapan dibatasi, tidak ada yang melakukannya dalam percakapan yang tidak dibatasi.