Впрочем, про машину Тьюринга я погорячился. ИППП НЕ Тьюринг-полное (полуразрешимое). А поскольку логика высшего порядка НЕ разрешимое, можно сказать, что доказательства в ней содержат "новую" информацию — а именно, "в какую сторону пойти", т.е. как устранить неразрешимость.
Ну ещё можно вспомнить вычислительную несводимость (computational irreducibility), которую, как я слышал, Стивен Вольфрам формализовал и доказал. С этой стороны ряд машин Тьюринга (и моделей попроще) порождают новую информацию в том смысле, что её нельзя заранее "предсказать", а можно только "обнаружить", пройдя все шаги вычисления до нужного.