Машина Тьюринга и Нормальные алгоритмы А.А. Маркова

↑

▷ Содержание

Стр 1 из 3Следующая ⇒

Машина Тьюринга и Нормальные алгоритмы А.А. Маркова

Машина Тьюринга (МТ)

Алан Тьюринг в 1936 году опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешений», которая наравне с работами Э.Поста и А.Чёрча лежит в основе теории алгоритмов. История создания этой работы связана с формулировкой Давидом Гильбертом на Международном конгрессе математиков в Париже в 1900 году неразрешенных математических проблем. Одной из таких проблем была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как «проблему разрешимости» – нахождение общего метода для определения выполнимости данного высказывания на языке формальной логики.

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

«Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, то есть процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислимого процесса. Полученная модель вычислений, в которой каждый алгоритм разбивается на последовательность простых, элементарных шагов и была логической конструкцией, названной впоследствии машиной Тьюринга». (Джон Хопкрофт)

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

Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную деятельность. Такой человек, находясь в определенном «умонастроении» (состоянии), просматривает некий текст. Затем он вносит в этот текст какие-то изменения, проникается новым «умонастроением» и переходит к просмотру последующих записей.

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

МТ располагает конечным числом знаков, образующих внешний алфавит А = {а₀, а₁, … , а_п}. В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита А. Удобно считать, что среди букв внешнего алфавита А имеется так называемая «пустая» буква, которая записывается в пустую ячейку ленты. Как правило, символом пустой ячейки являются буквы а₀, е или 0 (если не используется десятичный алфавит). Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.

В каждый момент времени МТ способна находиться в одном состоянии из конечного числа внутренних состояний Q = {q₀, q₁, … , q_m}. Среди состояний всегда имеются два: q₁ – начальное состояние (находясь в этом состоянии, МТ начинает работу) и q₀ – заключительное или состояние останова (попав в него, МТ прекращает работу).

Работа МТ определяется программой или функциональной схемой или функцией переходов d, которая задается отображением пары из декартова произведения множеств Q х А (множество упорядоченных пар, первый элемент которых берется из множества Q, а второй элемент – из множества А) в тройку из декартова произведения Q х А х Х, где Х = {П, Л, С} – множество переходов МТ по ленте (П – переход вправо на одну ячейку, Л – переход влево на одну ячейку, С – МТ остается на месте (в программе часто этот символ не пишется)).

Решаемая проблема задается путем записи конечного числа символов из множества А на ленту.

…

е

е

а₁

а₂

а₃

е

е

…

Работа МТ: Находясь в какой-либо момент времени в незаключительном состоянии (q_i ≠ q₀), МТ совершает шаг, который полностью определяется ее текущим состоянием q_i и символом а_j, воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой T(i, j): q_iа_j→ q_kа_lX, Х = {П, Л, С}. Шаг заключается в том, что:

1. содержимое а_j обозреваемой на ленте ячейки стирается и на его место записывается символ а_l, который может совпадать с а_j;

2. машина переходит в новое состояние q_k, которое также может совпадать с предыдущим состоянием q_i;

3. машина переходит к обозрению следующей правой ячейки, если Х = П, или следующей левой ячейки, если Х = Л или остается на месте, если Х = С (или нет никакого символа).

В следующий момент времени, если q_k ≠ q₀, машина делает шаг, регламентированный соответствующей командой T(k; l).

Поскольку работа машины, по условию, полностью определяется ее состоянием q_i и содержимым а_j, обозреваемой в этот момент времени ячейки, то для каждых q_i и а_j (i = 1, … , m; j = 1, … , n) программа машины должна содержать единственную команду, начинающуюся символами q_i а_j. Поэтому программа МТ с внешним алфавитом А и алфавитом внутренних состояний Q содержит не более чем т(п + 1) команду.

Словом в алфавите А, в алфавите Q или в алфавите АÈQ называется последовательность букв соответствующего алфавита.

Под k-конфигурацией будем понимать изображение ленту МТ с информацией, сложившейся на ней к началу k-го шага или слово в алфавите АÈQ, записанное на ленту к началу k-го шага с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина (00011101q₁110 – в состоянии q₁ обозревается вторая с правого края непустого слова ячейка с записанным на ней символом 1).

Имеют смысл лишь конечные конфигурации.

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

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

Говорят, что непустое слово a в алфавите А воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все остальные ячейки пусты (в них записаны пустые буквы) и МТ обозревает крайнюю справа ячейку из тех, в которых записано слово a.

Стандартное положение называется начальным (заключительным), если МТ, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (в заключительном состоянии q₀).

Говорят, что слово a перерабатывается машиной в слово b (a→b), если от слова a, воспринимаемого машиной в стандартном начальном положении (СНП), МТ, после выполнения конечного числа команд, приходит к слову b, воспринимаемому в положении остановки.

Познавательные статьи:



Техника нижней прямой подачи мяча

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

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов