Лекции

АВМ (аналоговые вычислительные машины), или вычислительные машины неп-

рерывного действия, работают с информацией, представленной в непрерывной (аналоговой) форме, то есть в виде непрерывного ряда значений какой-либо физической величины (чаще всего электрического напряжения). АВМ иначе называют моделирующими установками, или электронными моделями. Решение задач, или моделирование, на АВМ сводится к составлению и решению уравнения (или системы уравнений) для моделируемого процесса.

АВМ в основном строятся на электрических и электронных элементах постоянного тока. Переменные (функции) представляются в АВМ с помощью напряжений постоянного тока. Хотя для построения модели может использоваться любой другой физический процесс, описываемый теми же математическими зависимостями, что и моделируемый процесс.

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

умножение на постоянный коэффициент;

изменение знака (инвертирование в аналоговом смысле);

алгебраическое сложение;

интегрирование (во времени);

дифференцирование (во времени).

ABM весьма просты и удобны в эксплуатации. Программирование задач для решения на этих машинах, как правило, не трудоемкое. Скорость решения задач изменяется по желанию оператора и может быть сделана сколь угодно большой (больше, чем у ЦВМ), но точность решения задач очень низкая (относительная погрешность до 2-5 %).

ГВМ (гибридные вычислительные машины), или вычислительные машины ком-

бинированного действия, работают с информацией, представленной и в цифровой, и в аналоговой форме, они совмещают в себе достоинства АВМ и ЦВМ. ГВМ целесообразно использовать для решения задач управления сложными быстродействующими техническими комплексами.

Аналоговые ЭВМ в настоящее время вытеснены цифровыми ЭВМ практически во всех сферах применения. Даже прием и формирование непрерывных сигналов часто выполняют на цифровых ЭВМ, оснащенных входными и выходными преобразователями аналоговых сигналов в цифровую форму и обратно.

1.9.2. Универсальные, проблемно-ориентированные и специализированные ЭВМ.

По назначению компьютеры можно разделить на три группы: универсальные (общего назначения), проблемно-ориентированные и специализированные.

Универсальные компьютеры предназначены для решения самых различных инже- нерно-технических, экономических, математических, информационных и им подобных задач, отличающихся сложностью алгоритмов и большим объемом обрабатываемых данных. Они широко применяются в вычислительных центрах коллективного пользования и в других мощных вычислительных комплексах. Характерными чертами универсальных компьютеров являются:

высокая производительность;

разнообразие форм обрабатываемых данных: двоичные, десятичные, символьные – при большом диапазоне их изменения и высокой точности их представления;

обширная номенклатура выполняемых операций, как арифметических, логических, так и специальных;

большая емкость оперативной памяти;

развитая организация системы ввода-вывода информации, обеспечивающая подключение разнообразных видов внешних устройств.

Проблемно-ориентированные компьютеры предназначены для решения более узко-

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

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

1.9.3. Суперкомпьютеры, суперЭВМ, большие, малые и микроЭВМ.

По размерам и вычислительной мощности компьютеры можно разделить на суперкомпьютеры (суперЭВМ), большие, малые и микрокомпьютеры (микроЭВМ).

Функциональные возможности компьютеров обусловлены такими важнейшими техни- ко-эксплуатационными характеристиками:

быстродействие;

разрядность и формы представления чисел, которыми оперирует компьютер;

номенклатура, емкость и быстродействие всех запоминающих устройств;

номенклатура и технико-экономические характеристики внешних устройств хранения, обмена и ввода-вывода информации;

типы и пропускная способность устройств связи и сопряжения узлов компьютера между собой (тип внутримашинного интерфейса);

способность компьютера одновременно работать с несколькими пользователями и выполнять параллельно несколько программ (многозадачность);

типы и технико-эксплуатационные характеристики операционных систем, используемых в машине;

наличие и функциональные возможности программного обеспечения;

способность выполнять программы, написанные для других типов компьютеров (программная совместимость с другими типами компьютеров);

система и структура машинных команд;

возможность подключения к каналам связи и к вычислительной сети;

эксплуатационная надежность компьютера;

коэффициент полезного использования компьютера во времени, определяемый соотношением времени полезной работы и времени профилактики.

Исторически первыми появились большие ЭВМ, элементная база которых прошла путь от электронных ламп до интегральных схем со сверхвысокой степенью интеграции. Большие компьютеры за рубежом часто называют мэйнфреймами (mainframe) и к ним относят, как правило, компьютеры, имеющие:

производительность не менее 100 MIPS;

основную память емкостью от 512 Мбайт до 1 Гбайта;

внешнюю память не менее 100 Гбайт;

многопользовательский режим работы (обслуживают одновременно от 16 до 1000 пользователей).

Основные направления эффективного применения мэйнфреймов – решение научнотехнических задач, работа в вычислительных системах с пакетной обработкой информации, работа с большими базами данных, управление вычислительными сетями и их ресурсами. Последнее направление – использование мэйнфреймов в качестве больших серверов вычислительных сетей – часто отмечается специалистами как наиболее актуальное.

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

MFlop/s.

Первый суперкомпьютер был задуман в 1960 и создан в 1972 году (машина ILLIAC IV с производительностью 20 MFLOPS). Начиная с 1975 года лидерство в разработке суперкомпьютеров захватила фирма Cray Research, выпустившая Cray 1 с производительностью 160 MFLOPS и объемом оперативной памяти 8 Мбайт, а в 1984 году – Cray 2, в полной мере реализовавший архитектуру с массовым параллелизмом микропроцессоров и ознаменовавший появление нового поколения суперкомпьютеров. Производительность Cray 2

– 2000 MFLOPS, объем оперативной памяти – 2 Гбайт (классическое соотношение, ибо критерий сбалансированности ресурсов компьютера – «каждому мегафлопсу производительности процессора должно соответствовать не менее 1 Мбайт оперативной памяти»).

По состоянию на ноябрь 2012 года, когда была опубликована 40-ая редакция списка 500 наиболее мощных компьютеров мира (www.top500.org) на первом месте списка созданный в США гибридный кластер Titan, базирующийся на платформе Cray XK7 с процессорами Opteron и NVIDIA K20x. Количество вычислительных ядер компьютера составляет 560640, пиковая производительность – до 27,11 PFLOPS, а производительность на тесте Linpack – до 17,59 PFLOPS. Стоить отметить потребляемую мощность этого кластера, она составляет 6,2 МВт.

В данной редакции списка Россия представлена 5 системами. На 26-ом месте находится суперкомпьютер МГУ «Ломоносов» производства компании «Т-Платформы», установленный в Научно-исследовательском вычислительном центре МГУ имени М.В. Ломоносова, с пиковой производительностью 1,7 PFLOPS и производительностью на тесте

Linpack 901,9 TFLOPS.

Появление в 70-х годах малых компьютеров обусловлено, с одной стороны, прогрессом в области электронной элементной базы, а с другой – избыточностью ресурсов больших ЭВМ для ряда приложений. Малые компьютеры используются чаще всего для управления технологическими процессами. Они более компактны и существенно дешевле больших компьютеров. Дальнейшие успехи в области элементной базы и архитектурных решений привели к возникновению суперминикомпьютера – вычислительной машины, относящейся по архитектуре, размерам и стоимости к классу малых компьютеров, но по производительности сравнимой с большой ЭВМ.

Малые компьютеры (мини-ЭВМ) – надежные, недорогие и удобные в эксплуатации компьютеры, обладающие несколько более низкими по сравнению с мэйнфреймами возможностями. Мини-компьютеры (и наиболее мощные из них суперминикомпъютеры) обладают следующими характеристиками:

производительность – до 1000 MIPS;

емкость основной памяти – до 8 Гбайт;

емкость дисковой памяти – до 1000 Гбайт;

число поддерживаемых пользователей – 16-1024.

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

Родоначальником современных мини-компьютеров можно считать компьютер PDP-11 фирмы DEC (США), он явился прообразом и наших отечественных мини-ЭВМ – системы малых ЭВМ (СМ ЭВМ): СМ 1, 2, 3, 4, 1400, 1700 и т. д. В настоящее время семейство ми- ни-компьютеров PDP-11 включает большое число моделей, начиная от VAX-11 до VAX3600, мощные модели мини-компьютеров класса 8000 (VAX-8250, 8820), супермиником-

пьютеры класса 9000 (VAX-9410, 9430) и т.д.

Изобретение в 1969 году микропроцессора (МП) привело к появлению в 70-х годах еще одного класса компьютеров – микрокомпьютеров. Именно наличие МП послужило первоначально определяющим признаком микрокомпьютеров. Сейчас микропроцессоры используются во всех без исключения классах компьютеров. Микрокомпьютеры весьма многочисленны и разнообразны. Среди них можно выделить несколько подклассов:

Многопользовательские микрокомпьютеры – это мощные микрокомпьютеры,

оборудованные несколькими видеотерминалами и функционирующие в режиме разделения времени, что позволяет эффективно работать на них сразу нескольким пользователям.

Персональные компьютеры (PC) – однопользовательские микрокомпьютеры, удовлетворяющие требованиям общедоступности и универсальности применения.

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

Серверы (server) – многопользовательские мощные микрокомпьютеры в вычислительных сетях, выделенные для обработки запросов от всех рабочих станций сети.

Сетевые компьютеры (network computer) – упрощенные микрокомпьютеры, обеспечивающие работу в сети и доступ к сетевым ресурсам, часто специализированные для выполнения определенного вида работ (защита сети от несанкционированного доступа, организация просмотра сетевых ресурсов, электронной почты и т. д.).

1.9.4. Направления исследований в области создания ЭВМ нового типа.

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

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

Криоэлектронные элементы (использующие эффект сверхпроводимости при низких температурах) также являются предметом исследований в течение ряда десятилетий. Для них также разработан функционально полный набор логических элементов и элементы памяти. Однако заметного практического использования в вычислительных системах эти технологии также пока не нашли. Не было и ожидаемого роста их применения и в связи с работами физиков в области, так называемой, высокотемпературной (до -80°С) сверхпроводимости в конце 1980-х годов.

Работы в области биоэлектроники также вызывают значительный интерес. Однако, несмотря на более, чем тридцатилетнюю историю, только в последнее время стали появляться сообщения об использовании разработок в этой области на практике. Но речи о вычислительных средствах пока не идет. В основном, биоэлектронные компоненты используются в системах идентификации и для частичного замещения утраченных органов.

В квантовых компьютерах для хранения и обработки информации используются различные физические эффекты, связанные с состоянием элементарных частиц и/или атомов. Это позволяет, используя квантовые эффекты, многократно увеличить скорости преобразований и объемы хранимой информации. Идею таких компьютеров относят к началу 1980-х годов. С начала 1990-х годов ведутся исследовательские работы в данной области во многих странах мира. Практическое использование таких компьютеров ожидается в обозримом будущем.

Принцип работы такого компьютера связан с квантовыми свойствами атомов и других частиц. Квантовый компьютер, в частности, может быть основан на спинах электронов и атомных ядер и на странных свойствах квантовых частиц в момент, когда их не наблюдают, иметь спин одновременно разных направлений. Когда спин частицы направлен вверх, атом может быть «считан» как 1, а направление вниз будет соответствовать 0. Это аналогично традиционному транзистору, в котором нули и единицы соответствуют включенному и выключенному состояниям, промежуточных состояний у классического бита не бывает. Но что делает квантовый компьютер уникальным, так это тот факт, что квантовые частицы, даже будучи очень хорошо изолированными, друг от друга, могут находиться в запутанном состоянии, в котором частицы все-таки зависят друг от друга.

В классическом компьютере изменение состояния отдельного бита никак не связано с изменением состояния всех остальных битов, разве что только одного. В квантовом компьютере управление состоянием одной частицы вызывает изменение состояния всех других. Это и приводит к так называемому квантовому параллелизму вычислений. Благодаря этому эффекту квантовый компьютер может иметь феноменальную производительность. Для определенных типов вычислений, подобных сложным алгоритмам для криптографии или поискам в гигантских массивах данных, квантовый компьютер может использовать «в

тандеме» сотни атомов. На обычном компьютере это бы соответствовало выполнению миллиардов операций одновременно [http://nature.web.ru/db/msg.html?mid=1151173&s=].

АЛГОРИТМИЧЕСКИЕ ОСНОВЫ ЭВМ

1.1. Общие положения.

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

лаемого результата.

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

Рассуждения такого рода приводят к фундаментальному понятию алгоритма – конечного набора предписаний, определяющих решение задачи посредством конечного количества операций.

Происхождение термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787–850) выдающегося математика средневекового Востока. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними.

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

Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

Понятность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для различных трактовок.

Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

Детерминированность (определенность) – выполнение алгоритма на одинако-

вых данных приводит к совпадению результатов.

Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Любая алгоритмически разрешимая вычислительная задача проходит несколько этапов при решении: от исходной постановки, через алгоритм, к выполнению на ЭВМ.

Каждый вычислительный алгоритм имеет дело с данными – входными, промежуточными, выходными. Для того чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора во многих алгоритмических языках: идентификатор – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах – наиболее обычный тип алгоритмических данных, а число символов в слове – естественная мера объема данных. Другой случай алгоритмических объектов – формулы. Примером могут служить формулы булевой алгебры.

Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм. После этого можно дать уточненное понятие алгоритма:

Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода, от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности и массовости.

Процесс обработки данных представляется на внешнем и внутреннем уровне. На внешнем уровне он представляется в виде алгоритма. Конкретный вид алгоритма зависит от используемого алгоритмического языка. На внутреннем уровне каждый такой процесс представляет собой последовательность логических операций и называется программой.

Программа – это запись алгоритма в форме, воспринимаемой ЭВМ. Любая программа состоит из отдельных команд. Каждая команда предписывает определенное действие и указывает, над какими операндами это действие производится. Программа представляет собой совокупность команд, записанных в определенной последовательности, обеспечивающих решение задачи на ЭВМ. Сами логические операции кодируются с помощью средств машинного языка. Процесс, порождаемый алгоритмом в ВМ – называется вычис-

лительным процессом.

1.2. Машина Тьюринга.

Изучение машины МТ в данном курсе не преследует цель глубокого исследования понятия алгоритма, а только понимания того, что принципы работы всех современных ЭВМ основаны на этом важнейшем понятии.

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

Определение «компьютер общего назначения» может быть формализовано в требовании, чтобы конкретный компьютер был способен подражать поведению некоторой универсальной машины. Первым компьютером, удовлетворяющим такому условию, считается машина Z3, созданная немецким инженером Конрадом Цузе (доказательство этого факта было проведено в 1998 году).

Вплоть до 30-х годов прошлого столетия понятие алгоритма оставалось интуитивно понятным и имело скорее методологическое, а не математическое значение. Работая над известной проблемой Гильберта, Тьюрингу пришлось дать четкое определение понятия алгоритма. Отталкиваясь от интуитивного представления о нем как о процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга (Turing machine).

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

Алан Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Это предположение известно как тезис Чёрча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины). Следовательно, он может моделировать алгоритмы в любом формализме, и из этого тезиса следует, что все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности решения алгоритмических задач.

Разумеется, никто не занимается решением практических задач с помощью моделей машины Тьюринга, для практических задач существуют языки программирования. Тем не менее, она представляет для нас определенный практический интерес. Машина Тьюринга (МТ) состоит из двух частей – ленты и каретки (рис. 2.2.1):

Лента:

a

b

b

Λ

a

b

b

Λ

Λ

Каретка:

q

q

Рис.2.2.1. Графическое представление машины Тьюринга

Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a0,a1,…,an}. Любой алфавит содержит символ «пробел», который обозначается как a0 или Λ. Договоримся не отличать клетки с пустым содержимым и клетки содержащие символ «пробел». В связи с этим изображение ленты, показанное на рисунке справа, такое же, как и на рисунке слева. Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа Λ, поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку».

Каретка – это активная часть МТ. В каждый момент она размещается под одной из клеток ленты и может прочитать ее содержимое. Будем называть эту клетку видимой клеткой, а находящийся в ней символ – видимым символом. Содержимое соседних и других клеток каретка не видит. Кроме того, в каждый момент каретка находится в одном из состояний, которые будем обозначать буквой q Q={q0,q1,…,qm}. Среди всех состояний выделяют два. В начале работы МТ находится в состоянии q1. Состояние q0 (будем также обозначать его восклицательным знаком «!») – это конечное состояние, попав в него, МТ заканчивает работу.

Пару из видимого символа a и текущего состояния каретки q будем называть конфигурацией и обозначать <a,q>. Каретка может выполнять три элементарных действия:

1.Записывать в видимую клетку новый символ (менять содержимое других клеток каретка не может).

2.Сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток каретка не может).

3.Переходить в новое состояние.

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

1.Записывает некоторый символ a′ в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется).

2.Сдвигается на одну клетку влево (обозначение – L), либо на одну клетку вправо (обозначение – R), либо остается неподвижным (обозначение – N).

3.Переходит в некоторое состояние q′ (в частности, может остаться в прежнем состоянии).

Формально действия одного такта будем записывать в виде тройки: <a′, [L,R,N], q′>, где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт <*, L, q1> означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q1.

1.3. Программа для машины Тьюринга.

Машина Тьюринга управляется программой. Программа – это таблица, строки в таблице соответствуют символам выбранного алфавита A, а столбцы – состояниям автомата Q. В начале работы машина Тьюринга находится в состоянии q1. В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей:

символ из алфавита A;

направление перемещения;

новое состояние автомата.

	q1	…	qj	…	qm
a1
a2
…
ai			a′, [L,N,R], q′
…
an
a0