August 30th, 2008

Заваровский

Типографская сложность теории

В своей статье "Противоречие и существование" я рассматривал такое понятие, как длина доказательства. Эта длина там измеряется в количестве формул в формальном выводе, минимальную длину такого вывода естественно рассматривать как меру сложности доказательства. С практической точки зрения даже короткие в этом смысле доказательства могут оказаться необозримо длинными. К примеру, рассмотрим формулу:Collapse )