Читать «Большая Советская Энциклопедия (ТЬ)» онлайн - страница 6
БСЭ БСЭ
Тьюринг Алан Матисон
Тью'ринг(Turing) Алан Матисон (23.6.1912, Лондон, — 7.6.1954, Уилмслоу, близ Манчестера), английский математик. Член Королевского общества (1951). По окончании Кембриджского университета (1935) работал над докторской диссертацией в Принстонском университете в США (1936— 1938). В 1939—45 сотрудник Британской иностранной службы, в 1945—48 — Национальной физической лаборатории, в 1948—54 — Манчестерского университета. Основные работы по математической логике и вычислительной математике; в 1936—1937 ввёл математическое понятие уточнённого абстрактного эквивалента
Тьюринга машина
Тью'ринга маши'на,название, закрепившееся за абстрактными (воображаемыми) «вычислительными машинами» некоторого точно охарактеризованного типа, дающими пригодное для целей математического рассмотрения уточнение общего интуитивного представления об
Т. м. удобно представлять в виде некоторого автоматически действующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью — лентой. Среди состояний имеются два выделенных — начальное и заключительное. Лента разделена на клетки (ячейки) и не ограничена влево и вправо. В каждой клетке ленты может быть записан любой из символов, входящих в некоторый заранее заданный перечень (ради единообразия считают, что в пустой клетке записана «пустая буква»). В каждый момент времени Т. м. находится в одном из своих состояний и, рассматривая (посредством специального устройства) одну из клеток своей ленты, воспринимает записанный в ней символ. Если в текущий момент времени Т. м. находится в не заключительном состоянии, то в следующий за ним момент: 1) она переходит в новое состояние, быть может совпадающее со старым, или заключительное; 2) в рассматриваемой клетке старый символ заменяется новым, быть может пустым или совпадающим со старым; 3) лента машины сдвигается на одну клетку влево или вправо либо остаётся на месте. Этот шаг Т. м. вполне определяется её текущим состоянием и текущим воспринимаемым символом. Таблица, содержащая полное перечисление возможных шагов данной Т. м., называется программой этой машины.