Часть математиков не теряла надежды найти решение ТЧК. Результаты, полученные А. Кемпе и П. Хивудом в XIX веке, а также Д. Биркгофом и Ф. Франклином в XX веке, послужили тем фундаментом, который позволил Г. Хишу формализовать известные методы доказательства сводимости конфигураций и показать, что, по крайней мере, один из них (прямое обобщение метода, использованного А. Кемпе) представляет собой процедуру, которую может осуществить ЭВМ [10]. Теория сводимых конфигураций, развитая Г. Хишем, к концу 80- годов XX века позволила уяснить необходимые для доказательства ТЧК идеи сводимости. Однако на пути доказательства ТЧК стояли еще два препятствия: недостаточный для доказательства ТЧК объем памяти существующих ЭВМ и неясность того, каков должен быть верхний предел необходимости для доказательства ТЧК сводимых конфигураций. Решающий шаг был сделан К. Аппелем и В. Хакеном.
Вначале К. Аппелем и В. Хакеном было найдено множество сводимых конфигураций, «размер кольца которых был достаточно мал, чтобы машинное время на доказательство сводимости было в пределах разумного» [10, р. 115]. Это позволило к концу 1972 года составить машинную программу для выполнения специального типа разряжающей процедуры. Прогонки этой программы позволили ее модифицировать при сохранении основной структуры. Это позволило на основе новой разряжающей процедуры построить множество сводимых конфигураций, в результате чего в конце 1976 года ТЧК была доказана (на что потребовалось 1200 часов машинного времени трех ЭВМ).
Таким образом, оказалось, что существуют такие математические утверждения, проверка которых требует объема вычислений и затрат времени, превышающих возможности не только отдельного человека, но и большого коллектива. Поэтому использование ЭВМ для решения подобных задач не только возможно, но и необходимо. Известно, что в традиционных доказательствах могут быть опущены некоторые моменты по причине их очевидности. Допускаются также ссылки на работы, в которых можно найти то, что пропущено в доказательстве. В том и другом случае подразумевается, что пропущенное может быть при желании восполнено. Использование же ЭВМ в математическом доказательстве создает ситуацию, в которой такой очевидной возможности нет.
Многие математики исходят из того, что доказательство должно обладать такими характеристиками, как убедительность, обозримость и формальность. Убедительность доказательства - это свидетельство понимания математики как человеческой деятельности. Обозримость - свидетельство возможности проверить (обозреть) его во всей полноте человеком, т.е. обозримость конкретизирует убедительность, связывая процесс доказательства с его субъектом. Традиционно источником убедительности доказательства считается ясность, т.е. возможность проверить его квалифицированным математиком без использования ЭВМ, хотя некоторые доказательства могут быть весьма длинными, и потребовать много сил и времени. Формальность доказательства означает представимость его в виде конечной последовательности формальной теории, удовлетворяющей некоторым условиям, т.е. это вывод заключения из аксиом теории с помощью правил логики. Формализованное^ доказательства, в свою очередь, конкретизирует обозримость, разбивая ее на конечные обозримые модели.
Когда в доказательстве присутствуют обозримость и формальность, это решающий аргумент в пользу признания доказательства математиками. Большинство их полагает, что все обозримые доказательства могут быть формализованными, хотя интуиционисты отрицают возможность замены актуальных конструкций математических доказательств формальными системами. Кроме того, теорема Геделя свидетельствует о том, что ни одна теория не в состоянии формализовать каждое доказательство. В таком случае ясно, что обозримое доказательство можно формализовать в более сильной формальной теории, но в последней будут содержаться новые обозримые доказательства, которые в ее рамках не могут быть формализованы.
