Описание тега turing-complete
Модель вычислений называется полной по Тьюрингу, если она способна моделировать машину Тьюринга. Языки программирования, полные по Тьюрингу, по крайней мере так же мощны, как самые мощные модели допустимых вычислений, о которых когда-либо говорилось.
Полная система Тьюринга означает систему, в которой может быть написана программа, которая найдет ответ (хотя и без каких-либо гарантий относительно времени выполнения или памяти) 1.