Несколько раз в топиках встречался сабж применительно к языку программирования. AFAIK, полнота какой-либо формальной логики - означает, что есть набор аксиом+правил вывода, а все остальное может быть выведено из этих аксиом посредством механизма вывода. Например, исчисление высказываний полно. Что означает полнота ЯП?