1.3. Машины Тьюринга и Поста

 

1.3.1. Основные понятия

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

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

Это было сделано в 1936-1937г. Постом и Тьюрингом независимо друг от друга и почти одновременно с работами Чёрча.

Основная идея Поста и Тьюринга заключалась в том, что:

алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».

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

Под машинами Поста и Тьюринга понимается некоторая гипотетическая машина, состоящая из следующих частей:

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

«считывающей головки» (СГ) – специального элемента, способного обозревать содержимое ячеек. В каждый момент времени СГ доступна одна ячейка, ИЛ можно перемещать вправо и влево

управляющего устройства (УУ), которое в каждый рассматриваемый момент находится в некотором «состоянии». Предполагается, что УУ может находиться в некотором конечном числе состояний. Одно из состояний называется заключительным и в работе машины играет особую роль, так как оно управляет окончанием работы машины.

Схематично машина может быть представлена следующим образом:

Рассмотрим теперь алгоритмическую систему, предложенную Постом.

В алгоритмической системе Поста информация представляется в двоичном алфавите А=(1,0 ). Таким образом, в каждой ячейке ИЛ можно поместить либо 0, либо 1.

Алгоритмы представляются в виде конечного упорядоченного набора правил, называемых приказами(командами). Работа алгоритма начинается с некоторой начальной ячейки, соответствующей первому приказу алгоритма. Составляющие алгоритм приказы могут принадлежать к одному из шести приказов, выполняемых УУ машины Поста:

1.Записать в рассматриваемую ячейку «1» и перейти к i-му приказу;

2.Записать в рассматриваемую ячейку «0» и перейти к i-му приказу;

3.Сдвинуть ИЛ вправо на одну ячейку и приступить к выполнению i-го приказа;

4.Сдвинуть ИЛ влево на одну ячейку и приступить к выполнению i-го приказа;

5.Если в рассматриваемой ячейке записана «1», то перейти к выполнению j-го приказа, а если записан 0, то перейти к выполнению i-го приказа;

6.Окончание работы алгоритма (останов)

Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста.

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

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

МТ, как и МП, может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным, или может изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной.

МТ называется стандартной, если она при сдвиге может предварительно изменить состояние воспринимаемой ячейки.

Пусть алфавит МТ задан в виде множества A=(S0,S1,….Sn)

где S0 соответствует пустой ячейке, а состояния УУ заданы в виде множества Q=(q0,q1,…qm), где q0 соответствует заключительному состоянию.

Конечная совокупность символов алфавита, с которым работает МТ, называется внешним алфавитом, а конечная совокупность состояний УУ – внутренним алфавитом.

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

Конфигурация задается в виде слова, описывающего конкретное состояние машины.

Пусть в некоторый момент времени МТ находится в состоянии, представленном на схеме:

S0

Sj

Sj

Sj

Sj

Sj

Sj

S0

1 2 3 …… k r-1 r

Конфигурация машины для данного случая будет представлена в виде слова:

S0Sj₁Sj₂ …..q_iSj_k…… Sj_r S0 …,где S0-символ, соответствующий пустой ячейке;

r-число заполненных ячеек на ИЛ;

Sj₁-состояние 1-го символа каждой ячейки;

Sj_k-состояние ячейки, просматриваемой в данный момент времени;

q_i-состояние УУ.

Каждая конфигурация содержит лишь одно вхождение символа q_i из внутреннего алфавита.

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

Если стандартная МТ, находясь в состоянии q_i и воспринимая записанный на ленте символ Sk , переходит в новое состояние q_j, осуществляя при этом замену символа в рассматриваемой ячейке на символ Sk и сдвиг ленты влево на одну ячейку, то говорят, что машина выполняет команду:

q_iSk q_jSm Л.

Если замена символа отсутствует, то Sm может отсутствовать.

Примем следующие обозначения:

Л-движение ленты влево,

П-движение ленты вправо,

С-нет движения.

Рассмотрим пример МТ с алфавитом A={0,1}, Q={q₀, q₁ } и командами:

q₁1 q₁1Л,

q₁0 q₀1С.

Пусть на информационной ленте имеется слово 11100. Считывающая головка стоит над первой слева единицей. В результате работы МТ это слово превратится в 11110. По окончании работы считывающая головка будет стоять над самой правой единицей.

Стандартная МТ в внешним алфавитом A={0,1} называется нестирающей, если она способна выполнять лишь команды вида:

q_α0 q_βaT;

q_α1 q_β1T; где a={0,1}, T={С,Л,П}, то есть она может записать 1, но не может удалить 1, если она уже вписана.

Совокупность всех команд, которые может выполнить МТ, называется ее программой.

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

Пусть МТ задана:

-внешним алфавитом A={S0,a,b,c,d},

-внутренним алфавитом Q={q0,q1,q2,q3,q4,q5}

и совокупностью команд:

q₀a q₁aЛ

q₀b q₀bЛ

q₂a q₅dП

q₀c q₀cЛ

q₁d q₂cП

q₂a q₄dП

q₄b q₂cП

Пустая ячейка -S0, заключительное состояние – q₅.

Рассмотрим применение данной машины для преобразования исходного слова bcadc в слово dcdcc.

Начальная конфигурация имеет вид:

q₀bcadc.

При этом машиной будет порождена следующая последовательность конфигураций:

1) q₀b q₀bЛ bq₀cadc

2) q₀c q₀cЛ bcq₀adc

3) q₀a q₁aЛ bcaq₁dc

4) q₁d q₂cП bcq₂acc

5) q₂a q₅dП bq₅cdcc

Как было сказано, на МТ оказалось возможным осуществить или имитировать все алгоритмические процессы, которые когда-либо описывались математиками.

Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций.

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

1.3.1.1.Машина Тьюринга с двумя выходами

Добавим в УУ машины Тьюринга состояние q*. Будем говорить, что если УУ переходит в состояние q₀ для заданного входного слова Х, то машина допускает слово Х.

Если УУ приходит в состояние q*, то машина запрещает слово Х. Такое устройство будем называть МТ с двумя выходами.

Оказывается, что если заданы две машины Т1 и Т2, которые допускают непересекающиеся множества Х1 и Х2, соответственно, то всегда можно построить МТ Т3 с двумя выходами, которые будут допускать Х1 и запрещать Х2.

Эти машины будут полезны при рассмотрении вопроса о разрешимости.

Множество разрешимо, если существует МТ с двумя выходами, которая допускает все элементы этого множества и запрещает элементы, не принадлежащие ему.

Предлагаю ознакомиться с аналогичными статьями: