Выдержка из книги
Булос Д.N.
Вычислимость и логика
Если используется лента, то какая: имеющая начало, но не имеющая конца или же бесконечная с обеих сторон. В зависимости от того, какие ответы будут даны на эти вопросы, понятие вычисления, если говорить о деталях, приобретет тот или иной вид. Наша задача, однако, состоит вовсе не в том, чтобы дать точное изображение отдельных шагов, из которых складывается вычисление, и, более того, класс функций, допускающих вычисление, оказывается, не зависит от того, какие ответы будут получены на эти вопросы. Имеющийся опыт работы с понятием вычислимости наводит на мысль, что основное содержание этого понятия не зависит от того, какие - достаточно правдоподобные - ответы будут приняты. Действительно, если взять любое другое точное и правдоподобное определение понятия вычисления из тех, которые были предложены, то можно аккуратно и строго доказать, что наше понятие вычислимости эквивалентно новому в том смысле, что всякая функция, вычислимая согласно одному из них, оказывается вычислимой и согласно другому. Но так как нет предела возможным вариациям в точном определении понятий вычислимости и эффективности, то следует в конце концов принять или отвергнуть тезис ( не допускающий математического доказательства) о том, что множество функций, вычислимых в нашем смысле, совпадает с множеством функций, доступных для вычисления машинами и людьми с использованием произвольных эффективных методов, если только игнорируются ограничения, связанные с нужными временем, скоростью и материалом. Хотя этот тезис ( известный как тезис Черча) недоказуем, он был бы опровержимым, если бы оказался ложным. Действительно, если он ложен, то существует функция, вычислимая в интуитивном смысле, но не вычислимая с нашей точки зрения.
