Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Гипотетические машины


Классическую возможность точнее охватить понятие алгоритма предоставляют (конфигураций) и множества переходов из одного состояния в другое, гипотетические машины. Они являются математическими образованиями, которые соответствуют математическому отражению пространства состояний и функции переходов реальных вычислительных машин.

Гипотетические машины, как и реальные, в общем случае состоят из множества состояний которые соответствуют отдельным шагам вычислений машины. Существует ряд гипотетических машин, среди которых:

·         конечные автоматы и

·         магазинные машины.

С помощью конечных автоматов невозможно получить достаточно общее понятие вычислимости. Уже магазинные машины являются более мощными, чем конечные автоматы, так как магазинные машины для любых КС-языков могут вычислять, принадлежит слово данному языку или не принадлежит. Поскольку магазинные машины, очевидно, представляют алгоритмы, то конечные автоматы недостаточно мощны, чтобы охватить понятие вычислимости.

Машины Тьюринга

Машина Тьюринга (короче, Т-машина) была предложена английским математиком Аланом Тьюрингом в 1936 г. как простая гипотетическая модель вычислительного устройства. Т-машина состоит из ленты для хранения знаков, головки для чтения/записи и устройства управления с конечным множеством управляющих состояний’•

Лента разбита на ячейки и считается бесконечной в обе стороны, однако всегда только конечный отрезок ленты должен нести существенную информацию для вычисления. Чтобы это выразить точнее, используется символ # как держатель места для пустой информации. Таким образом, на ленте Т-машины всегда имеется только конечное число знаков, отличных от #.

Машина Тьюринга (ТМ) работает следующим образом. На каждом шаге работы ТМ читает знак из той ячейки на ленте, которая находится под головкой чтения/записи. В зависимости от текущего состояния управления в данную ячейку записывается некоторый знак, управление переходит в новое состояние и головка смещается на одну ячейку влево или вправо или же сохраняет свою позицию.


Начало  Назад  Вперед



Книжный магазин