Cтраница 2
Если дано каноническое исчисление, то определим по индукции понятие вывода некоторого слова. [16]
В этом определении не предполагается, что множество Т задано эффективно, так что понятие вывода становится тоже неэффективным. [17]
Поэтому для получения аксиоматических теорий, полных относительно некоторого понятия истинности и являющихся расширениями конструктивного арифметического исчисления, следует рассматривать так называемые полуформальные теории, понятие вывода в которых уже не является разрешимым понятием. [18]
Последним и самым трудным вопросом является вопрос о достаточной общности предложенных определений алгоритма и вычислимой функции. Однако эта общность обманчива. В самом деле, чтобы сформулировать определение вычислимой в смысле А) функции, мы неизбежно ограничиваемся некото рым фиксированным исчислением с фиксированными правилами вывода. Если же поставить вопрос о выводе в произвольном исчислении, с произвольными правилами вывода, то следует учесть, что понятие вывода в исчислении в самом общем виде может быть уточнено лишь на базе уже уточненного понятия алгоритма. [19]