Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

и выполнено Проверка условия и и не выполнено Рис. 5.3. Повторение алгоритмов § 7. Машина Тьюринга Стремясь найти точное определение понятия алгоритма, Тьюринг выделил некоторый класс абстрактных машин, о которых высказал предположение, что они пригодны для осуществления любой "механической" вычислительной процедуры. Эти машины называются теперь в честь их изобретателя машинами Тьюринга. Пусть имеется лента, потенциально бесконечная в обе стороны* и разделенная на ячейки (квадраты), см. Рис. 5.4. So Потенциальная бесконечность ленты Рис. 5.4. понимается в том смысле, что в каждый данный момент времени она имеет конечную длину, и вместе с тем к ней всегда как слева, так и справа могут быть добавлены новые квадраты. Имеется некоторое конечное множество символов So,Si,..,S „, которое называется алфавитом машины. В каждой ячейке может быть записан только один из символов - буква алфавита машины. Машина обладает некоторым конечным множеством внутренних состояний {qo,qi,...,qm}- В каждый данный момент времени машина находится только в одном из этих состояний. Считаем, что внутренним состоянием qo обладает каждая машина и qo называется начальным состоянием. Машина имеет читающую головку, которая в каждый данный момент времени находится на одном из квадратов ленты и воспринимает символ, записанный на этом квадрате. Будем предполагать, что среди символов So,Si,..,Sn имеется символ, означающий пустой квадрат, например. So. Положим, ) Тьюринг определил машину с лентой потенциально бесконечной вправо и ограниченной слева. Потенциальная бесконечность ленты в обе стороны упрощает дальнейшее описание работы машины. Можно показать, что вводимая машина эквивалентна машине, определенной Тьюрингом. 157