Лекция № 3. Машины Тьюринга

1. Машины Тьюринга

2. Не распознаваемость самоприменимости машины Тьюринга

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

А.Тьюринг

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

Рис. 4. Представление машины Тьюринга.

В ячейку ленты может быть записана буква из алфавита A=0, a₁, a₂, … a_n>. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a₀ для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–0> воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово[5] (см. рис. 5).

a0

a0

a0

a0

a0

A0

a0

a0

Рис. 3. Стандартное положение в машине Тьюринга

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

Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой q_i из алфавита внутренних состояний – Q=0, q₁, q₂, ….q_m>. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q₀ в таком алфавите обозначается состояние остановки, а символом q₁ – начальное состояние. Из состояния q₁ машина начинает работать, а попав в состояние q₀, прекращает работу.

Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1£i£m, 0£j£n, i,jÎZ), именуемыми командами, каждаяиз которыхможет иметь следующий вид (см. таблицу 1).

Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1).

Таким образом, та или иная машина Тьюринга полностью определяется:

в) программой (функциональной схемой).

Команды машины Тьюринга
Формат команды	Описание команды
qiaj →qkapЛ	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку влево (Л).
qiaj →qkapП	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку вправо (П).
qiaj →qkap	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка остается на месте.

Говорят, что слово a перерабатывается машиной Тьюринга в слово b, если от слова a, воспринимаемого в начальном состоянии q₁, машина после выполнения конечного числа команд программы приходит к слову b, воспринимаемому в положении остановки.

Пример 3.1.1. Машина Тьюринга определяется функциональной схемой в виде следующей таблицы:

Q A	q1	q2	q3
a0	q31П	q1a0Л
q2a0Л	q21Л	q31П
*	q0a0	q2*Л	q31*П

Слово, воспринимаемое в начальном состоянии q₁ имеет вид:

Определим, в какое слово переработает это слово машина.

Так машина находится в состоянии q_1, обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q₁ и строки 1 функциональной схемы. Это команда q₂a₀Л. После ее выполнения машина перейдет в следующее состояние:

После выполнения следующей команды q₂*Л (записанной на пересечении столбца q₂ и строки 1)машина перейдет в следующее состояние:

На пересечении столбца q₂ и строки 1в функциональной схеме машины Тьюринга записана команда q₂1Л, выполнение которой приведет к состоянию:

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

Лекция № 3. Машины Тьюринга

Дата добавления: 2013-12-23 ; просмотров: 4036 ; Нарушение авторских прав

Q → D

Q0 → 0Q

Q1 → 1Q

Q Þ l

Q1 → 1Q

Q+ → Q

1→ 11,

10 → 00

THORN; 1

применим к словам:

а) a₀=00 (M₁(00)=00 – в функциональной схеме нет ни одной активной подстановки);

б) a₀=110 (M₁(110)=000 – дважды применяется вторая подстановка);

в) a₀=010 (M₁(010)=1 – применяется заключительная подстановка.

Этот же алгорифм не применим к словам: a₀=01; a₀=1; a₀=11 и т.д.

Вот еще два примера, заимствованных нами из [ ].

Пример 2.2.1. Алгорифм M₂ вычисления суммы чисел, записанных в унарной системе счисления в алфавите A₁= в виде 11+1 или 111+11+1 и т.п., работающий в алфавите A₂=A₁È, определяется следующей функциональной схемой:

l → Q.

Пример 2.2.2. Алгорифм M_3, работающий над алфавитом A₁= в алфавите A₂=A₁È и прибавляющий 1 к двоичному числу, имеет следующую функциональную схему:

1D → D0

0D Þ 1

D Þ 1

l → Q.

1. Машины Тьюринга

2. Не распознаваемость самоприменимости машины Тьюринга

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

А.Тьюринг

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

Рис. 4. Представление машины Тьюринга.

В ячейку ленты может быть записана буква из алфавита A=0, a₁, a₂, … a_n>. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a₀ для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–0> воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово[5] (см. рис. 5).

a0

a0

a0

a0

a0

A0

a0

a0

Рис. 3. Стандартное положение в машине Тьюринга

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

Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой q_i из алфавита внутренних состояний – Q=0, q₁, q₂, ….q_m>. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q₀ в таком алфавите обозначается состояние остановки, а символом q₁ – начальное состояние. Из состояния q₁ машина начинает работать, а попав в состояние q₀, прекращает работу.

Читайте также:  Внесение изменений после замены двигателя

Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1£i£m, 0£j£n, i,jÎZ), именуемыми командами, каждаяиз которыхможет иметь следующий вид (см. таблицу 1).

Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1).

Таким образом, та или иная машина Тьюринга полностью определяется:

в) программой (функциональной схемой).

Команды машины Тьюринга
Формат команды	Описание команды
qiaj →qkapЛ	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку влево (Л).
qiaj →qkapП	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку вправо (П).
qiaj →qkap	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка остается на месте.

Говорят, что слово a перерабатывается машиной Тьюринга в слово b, если от слова a, воспринимаемого в начальном состоянии q₁, машина после выполнения конечного числа команд программы приходит к слову b, воспринимаемому в положении остановки.

Пример 3.1.1. Машина Тьюринга определяется функциональной схемой в виде следующей таблицы:

Q A	q1	q2	q3
a0	q31П	q1a0Л
q2a0Л	q21Л	q31П
*	q0a0	q2*Л	q31*П

Слово, воспринимаемое в начальном состоянии q₁ имеет вид:

Определим, в какое слово переработает это слово машина.

Так машина находится в состоянии q_1, обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q₁ и строки 1 функциональной схемы. Это команда q₂a₀Л. После ее выполнения машина перейдет в следующее состояние:

После выполнения следующей команды q₂*Л (записанной на пересечении столбца q₂ и строки 1)машина перейдет в следующее состояние:

На пересечении столбца q₂ и строки 1в функциональной схеме машины Тьюринга записана команда q₂1Л, выполнение которой приведет к состоянию:

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