Sebagai contoh, bahasa pemrograman dan perangkat instruksi CPU adalah contoh dari sistem aturan formal yang mengakses dan memodifikasi data. Jika aturan dapat digunakan untuk mensimulasikan mesin komputasi hipotetis Turing, aturan tersebut dikatakan "Turing lengkap." Sistem Turing-complete dapat dibuktikan secara matematis untuk dapat melakukan perhitungan atau program komputer apa pun.
Contoh sistem lengkap Turing adalah kalkulus lambda yang dikembangkan oleh Gereja Alonzo, profesor Alan Turing.
Contoh sistem lengkap Turing
Ilmu Komputer, kalkulus Lambda, istilah Pemrograman