Числения, для чего надо задать начальное состояние машины и

Программу, которая эти вычисления сделает.

Машина Тьюринга (автор —математик А. Тьюринг, Англия) —абстракт-

Ная конструкция, предназначенная для определения понятия алго-

Ритма (если для решения задачи можно построить машину Тьюрин-

Га, то она алгоритмически разрешима). Машиной называется пото-

Му, что при построении используются некоторые понятия реальных

Машин —память, команда и пр. Машина Тьюринга состоит из не-

Ограниченной в обе стороны ленты, разделенной на ячейки, кото-

Глоссарий терминов и сокращений (русский язык) 465

Рые последовательно пронумерованы целыми числами, как поло-

Жительными, так и отрицательными. В каждой ячейке ленты может

Стоять любой символ из заданного алфавита, в котором выделен

≪пустой≫ символ —признак того, что ячейка пустая. Машина имеет

Конечное множество внутренних состояний, начальное (с него на-

Чинается работа машины) и конечное состояние, попав в которое,

Машина прекращает работу. Кроме ленты, имеется головка чте-

ния/записи, которая, во-первых, умеет двигаться вперед, назад и

Стоять на месте; во-вторых, умеет читать содержимое, стирать и за-

Писывать символы из данного алфавита; в-третьих, управляется

Программой. Программа представляет собой таблицу, в которой в

Каждой клетке записана команда. Каждая клетка определяется дву-

Мя параметрами —символом алфавита и состоянием машины. Ко-

Манда представляет собой указание, куда передвинуть головку чте-

ния/записи из текущего состояния, какой символ записать в теку-

Щую ячейку и в какое состояние перейдет машина.

Машинное слово —упорядоченное множество двоичных разрядов, ис-

Пользуемое для хранения команд программы и обрабатываемых

Данных. Каждый разряд, называемый битом, —это двоичное чис-

Ло, принимающее значения только 0 или 1. Разряды в слове обыч-