Cтраница 2
Доказательство этой теоремы совсем несложно, но громоздко, и мы поэтому его не приводим. Полезно, однако, уяснить смысл данной теоремы. Понятие нормально вычислимой функции было введено А. А. Марковым в качестве математического уточнения понятия алгоритмически вычислимой функции. Оно было введено независимо от понятия вычислимой функции и по своей исходной конструкции существенно от него отличается. Черча был бы опровергнут, поскольку такая функция была бы алгоритмически вычислимой ( в обычном понимании), но не вычислимой по Тьюрингу. Однако ввиду справедливости приведенной теоремы класс тех алгоритмически вычислимых функций, которые нормально вычислимы по Маркову, содержится в классе вычислимых функций, что служит косвенным подтверждением тезиса Черча. [16]
I-V настоящего тома кругу идей добавлен в виде Приложений ряд обособленных рассмотрений. Два Приложения дополняют материал, изложенный в гл. V: в Приложении II рассматривается уточнение понятия вычислимой функции, полученное в последнее время различными способами, и приводятся те относящиеся к этому кругу вопросов факты, которые легко могут быть изложены на основе материала, содержащегося в данной книге. В частности, приводится теорема А. [17]
Исходя из совершенно других предпосылок, Черч в 1936 г. вывел тот же класс числовых функций, что и Гедель. Черчем была сформулирована гипотеза о том, что класс рекурсивных функций тождествен с классом всюду определенных вычислимых функций. Эта гипотеза известна под именем тезиса Черча. Понятие вычислимой функции точно не определяется, поэтому тезис Черча доказать нельзя. [18]
Вейль дает здесь краткий и доступный обзор проблематики оснований математики в первой трети двадцатого века для общематематической аудитории, упоминая и некоторые более поздние результаты. Несколько более субъективно и эмоционально, чем другие точки зрения, описан подход самого Вейля к построению математического анализа, изложенный в книге Континуум, перевод которой включен в настоящий сборник. Так Вейль называет совокупность, которая настолько проста, что обеспечено выполнение законов обычной ( классической) логики для любых свойств ее элементов. Как отмечает сам Вейль, в основаниях математики преобладает экстенсиональная точка зрения, отождествляющая совокупности, состоящие из одних и тех же элементов. Вейль почти не касается конструктивного направления в математике, которое стало интенсивно развиваться после уточнения понятия вычислимой функции в конце тридцатых годов. [19]