ТЬЮРИНГА МАШИНА
название, закрепившееся
за абстрактными (воображаемыми) "вычислительными машинами" нек-рого
точно охарактеризованного типа, дающими пригодное для целей ма-тематич.
рассмотрения уточнение общего интуитивного представления об алгоритме.
Концепция такого рода машины сложилась в сер. 30-х гг. 20 в. у А. М. Тьюринга
в
результате произведённого им анализа действий человека, выполняющего в
соответствии с заранее разработанным планом те или иные вычисления, т.
е. последовательные преобразования знаковых комплексов.
Т. м. удобно представлять в виде нек-рого
автоматически действующего устройства, способного находиться в конечном
числе внутренних с о-стояний и снабжённого бесконечной внешней памятью
- лентой. Среди состояний имеются два выделенных - начальное и заключительное.
Лента разделена на клетки (ячейки) и не ограничена влево и вправо.
В каждой клетке ленты может быть записан любой из символов, входящих в
нек-рый заранее заданный перечень (ради единообразия считают, что в пустой
клетке записана "пустая буква"), В каждый момент времени Т. м. находится
в одном из своих состояний и, рассматривая (посредством специального устройства)
одну
из клеток своей ленты, воспринимает записанный в ней символ. Если в текущий
момент времени Т. м. находится в незаключительном состоянии, то в следующий
за ним момент: 1) она переходит в новое состояние, быть может совпадающее
со старым, или заключительное; 2) в рассматриваемой клетке старый
символ заменяется новым, быть может пустым или совпадающим со старым; 3)
лента
машины сдвигается на одну клетку влево или вправо либо остаётся на месте.
Этот ш а г Т. м. вполне определяется её текущим состоянием и текущим воспринимаемым
символом. Таблица, содержащая полное перечисление возможных шагов данной
Т. м., наз. программой этой машины.
Текущее полное описание Т. м. даётся
её конфигурацией, к-рая состоит из указания для данного момента следующей
информации: 1) конкретного заполнения клеток ленты символами, 2)
клетки,
находящейся в поле зрения машины, 3) состояния, в к-ром машина находится.
Если у данной Т. м. взять в качестве
исходной к.-л. конфигурацию с незаключительным состоянием, то р а б о-т
а этой машины будет заключаться в последовательном, шаг за шагом, преобразовании
исходной конфигурации в соответствии с программой машины до тех пор, пока
не будет достигнута конфигурация с заключительным состоянием. Эта последняя,
если она существует, и считается результатом работы данной Т. м. над исходной
конфигурацией.
Имеются серьёзные основания считать,
что понятие Т. м. доставляет адекватное уточнение общего представления
об алгоритме, т. е. что всякий алгоритм может быть промоделирован подходящей
Т. м. Соответствующее соглашение известно в алгоритмов теории под
названием тезиса Тьюринга. Теория Т. м. даёт удобный рабочий аппарат для
многих исследований, требующих точного понятия алгоритма. В частности,
ввиду естественности совершаемых ими шагов, Т. м. стали объектом пристального
внимания в теории сложности алгоритмич. вычислений. В ходе развития теории
Т. м. рассматривались различные их обобщения: напр., Т. м. с более общим
типом лент, с несколькими лентами, а также недетерминированные Т. м.
Лит.: К л и н и С. К., Введение
в метаматематику, пер. с англ., М., 1957; М е н-дельсон Э., Введение в
математическую логику, пер. с англ., М., 1971. Н.М. Нагорный.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я