Математическая логика и теория алгоритмов

Теорема 6.4. Повторение нормального алгоритма, управля­ емое нормальным алгоритмом, есть нормальный алгоритм. Основным и важнейшим результатом этого параграфа является то, что различные операции (комбинации) над нормальными алгорит­ мами снова приводят к нормальному алгоритму. § 7. Машина Тьюринга Стремясь найти точное определение понятия алгоритма, Тьюринг выделил некоторый класс абстрактных машин, о которых высказал предположение, что они пригодны для осуществления любой "механической" вычислительной процедуры. Эти машины называются теперь в честь их изобретателя машинами Тьюринга. Пусть имеется лента, потенциально бесконечная в обе стороны* и разделенная на ячейки (квадраты) (рис. 6.4). Потенциальная бесконечность ленты понимается в том смысле, что в каждый данный момент времени она имеет конечную длину, и вместе с тем к ней всегда как слева, так и справа могут быть добавлены новые квадраты. Имеется некоторое ко­ 5-0 нечное множество символов SQ,S],..,S „, которое называется алфавитоммашины. В каждой Рис. 6.4 ^ ячейке может быть записан только один из символов - буква алфавита машины. Машина обладает некоторым конечным множеством внутрен­ них с о с т о я н и й {qQ,qi,...,qm}- В каждый данный момент времени машина находится только в одном из этих состояний. Считаем, что Тьюринг определил машину с лентой потенциально бесконечной вправо и ограниченной слева. Потенциальная бесконечность ленты в обе стороны упрощает дальнейшее описание работы машины. Можно показать, что вводимая машина экви­ валентна машине, определенной Тьюрингом. 234