Exempelvis är programmeringsspråk och CPU-instruktionsuppsättningar exempel på formella regelsystem som åtkomst och modifiering av data. Om reglerna kan användas för att simulera Turings hypotetiska datormaskin, sägs reglerna vara "Turing complete." Ett Turing-komplett system kan bevisas matematiskt för att kunna utföra eventuella beräkningar eller datorprogram.
Ett exempel på ett Turing-komplett system är lambda-calculus som utvecklades av Alonzo Church, Alan Turings professor.
Exempel på Turing kompletta system
Datavetenskap, Lambda-kalkyl, Programmeringsvillkor