Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
4.1.3. Вычислимость
С помощью понятия машины Тьюринга формализуется интуитивное понятие вычислимости (а тем самым — интуитивное понятие алгоритма). Мы имеем в виду прежде всего психологическое пред- 68
Часть /. Предварительные сведения из логики и алгебры
ставление о вычислимости: вычислителю (обычно человеку) предлагаются некоторые исходные данные и сообщаются правила их обработки; он должен получить тот или иной результат, зависящий от этих данных. Нередко вычислитель-человек может заранее сказать, вычислим ли требуемый результат: ведь, как правило, он обладает определенным практическим опытом вычислительной работы. Так, известно, что
. число я не вычислимо, поскольку его десятичное представление бесконечно1);
приближенное значение числа я с недостатком вычислимо с точностью до 10-п при любом фиксированном п.
Однако в ряде случаев неизвестно, является ли требуемый результат вычислимым.
Заметим, что, говоря о вычислимости, мы отвлекаемся от естественных (физических) ограничений, характерных как для человека, так и для машины: для некоторых вычислений может понадобиться больше ячеек памяти, чем имеется элементарных частиц во всей нашей Галактике, и время, измеряемое миллиардами тысячелетий; тем не менее, невзирая на материальную неосуществимость подобных вычислений, можно видеть, что они представляют эффективный способ получить некоторый результат за конечное число шагов. Были предприняты некоторые математические исследования с целью выработать более реалистическое понятие вычислимости; однако, как бы то ни было, математические теории, имеющие дело с вычислимостью, не занимаются практическими вычислениями, такими, например, с какими имеет дело численный анализ.
Таким образом, представление о вычислимости, формализуемое с помощью точного понятия машины Тьюринга, является очень широким; мы увидим тем не менее, что даже в рамках этого широкого Понятия некоторые объекты, которые интуитивно кажутся «вычислимыми», на самом деле таковыми не являются.
§ 4.2. МАШИНЫ ТЬЮРИНГА
Итак, мы хотим формализовать понятие вычислимости. Один из способов сделать это состоит в рассмотрении некоторой идеализированной вычислительной машины. При этом, поскольку мы хотим иметь возможность высказывать о ней как можно больше математических утверждений, она должна быть как можно более простой. Поэтому наша идеализированная машина не будет резко отличаться по своему строению от реальных электронных вычислительных машин (ЭВМ).
') Обычно в теории алгоритмов термин «вычислимое действительное число» используется иначе — он обозначает число, для которого существует алгоритм нахождения его последовательных рациональных приближений с любой степенью точности, которая оценивается также эффективно. В этом смысле число я вычислимо. — Прим, ред. Гл. IV. Алгоритмы. Машины Тьюринга
69
Интересующий нас класс абстрактных машин был введен в рассмотрение еще в 1936 году (т. е. до создания первых электронных вычислительных машин) английским математиком и логиком д. Тьюрингом. И здесь, как во многих других областях, научная фантазия опередила действительность.
Впрочем, если говорить лишь о ее абстрактной схеме строения, оказывается, что машина Тьюринга не так уж далека от настоящих ЭВМ.
Верно, что у машины Тьюринга предполагается потенциально бесконечная память; однако если ЭВМ обладает внешней памятью на магнитной ленте или на дисках, причем мы располагаем достаточным количеством бобин ленты или запасом дисков, то ситуация оказывается практически такой же.
Верно, что машина Тьюринга читает за один ход лишь один символ; однако этот символ может иметь сложное значение.
Наконец, как и арифметическое устройство ЭВМ, машина Тьюринга имеет конечное число внутренних состояний. Ее поведение в каждый данный момент зависит от состояния, в котором она находится, и от того символа, который она получает в качестве внешней информации. Если отвлечься от того, что процесс ввода информации идеализирован и сведен к чтению одного атомарного символа на каждом шаге, то поведение машины Тьюринга не отличается от функционирования реальной ЭВМ.
4.2.1. Содержательное описание
Машина Тьюринга состоит из следующих частей:
Управляющее устройство, способное принимать некоторое число состояний, которые соответствуют различным комбинациям состояний внутренних элементов электронной машины (ячейки памяти, электронные схемы и т. п.).
Лента, на которой заранее помещены подлежащие обработке данные и на которую заносятся в ходе работы машины промежуточные результаты вычислений.
Все записи на ленте производятся с помощью букв некоторого алфавита. Лента разделена на ячейки, в каждой из которых может находиться не более одного символа. Число ячеек предполагается неограниченным в обе стороны.
Головка, выполняющая чтение и запись символов; она обеспечивает обмен информацией между лентой и управляющим Устройством. Головка может работать в каждый момент только с одной ячейкой ленты. При этом она может
заменять прочитанный символ другим символом;
