Abstract
<jats:p>В статье анализируется тезис Чёрча-Тьюринга в его сильной формулировке - «любой алгоритм может быть выполнен на машине Тьюринга» - который является либо тавтологией (определяет себя через собственное же определение), либо оказывается ложным в зависимости от принятого определения термина «алгоритм». Появление новых вариаций машин Тьюринга для расширенных моделей вычислений (с произвольным доступом к памяти, недетерминированной, вероятностной, квантовой, оракульной, обратимой) интерпретируется не как уточнение исходной модели, а как симптом её принципиальной неполноты. Предлагается новое определение алгоритма, независимое от машины Тьюринга, основанное на понятии конечной системы переписывания над конечным алфавитом с явно названным невыводимым примитивом. В рамках этого определения тезис Чёрча-Тьюринга переформулируется как проверяемая математическая гипотеза и показывается, что в своей исходной форме он верен лишь для детерминированного подкласса алгоритмов. Это не обесценивает классическую теорию - она остаётся строгой и содержательной, - но меняет её эпистемический статус: из теории вычислений вообще она превращается в теорию одного, пусть и важнейшего, частного случая.</jats:p>