Выдержка из книги
Булос Д.N.
Вычислимость и логика
Выполнив во всех деталях второй и третий шаги, описанные выше, вы установите, что все функции, вычисляемые на абаках, вычислимы и по Тьюрингу. Это добавляет убедительности тезису Черча, поскольку функции, вычисляемые на абаках, - это функции, допускающие вычисление на современных цифровых вычислительных машинах, если только при их рассмотрении отбросить ограничения, касающиеся числа и объема регистров оперативной памяти. Разумеется, сохраняется возможность того, что в один прекрасный день будут изобретены существенно отличные типы вычислительных машин - машины, которые при соответствующей идеализации оказались бы в состоянии вычислять функции, не вычислимые ни на абаках, ни на машинах Тьюринга. Не зная, как будут функционировать эти машины, мы не можем и решить, какая идеализация потребуется. Можно предположить, однако, что эта идеализация будет сходна с применявшейся нами при рассмотрении машин Тьюринга и абаков и касавшейся возможностей их памяти: машина Тьюринга имеет большее пространство на ленте, чем ей реально требуется, и, аналогично, абак обладает пространством в своих регистрах для неопределенного количества неопределенно длинных чисел. С математической точки зрения тезис Черча остается недоказанным. Скорее мы получаем подтверждение его убедительности, подобное тому, какое могла бы получить эмпирическая научная теория. Новые аргументы в пользу тезиса Черча содержатся в следующих двух главах.
