Вопрос 33

Поскольку машина Тьюринга - алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них: произведение, возведение в степень, итерацию.

Пусть заданы машины Тьюринга T₁ и Т₂, имеющие общий внешний алфавит A = {a₀, a₁, …, а_m} и внутренние состояния Q₁ = {q₀, q₁, ..., q_n} и Q₂ = {q₀, g₁, ..., q_t} соответственно. Композицией или произведением машины T₁ и машины Т₂ будем называть машину Т с тем же внешним алфавитом A = {a₀, a₁, …, а_m} и набором внутренних состояний Q = {q₀, q₁, …,q_n, q_n+1, …, q_n+t} и программой, эквивалентной последовательному выполнению программ машин Т₁ и Т₂:

T = T₁ * Т₂

Таким же образом определяется операция возведения в степень: n-й степенью машины T называется произведение T... Т с n сомножителями.

Операция итерации применима к одной машине и определяется следующим образом. Пусть машина Т₁ имеет несколько заключительных состояний. Выберем ее r-е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина является результатом итерации машины Т₁: T = Т₁.

Альтернативное представление машины Тьюринга в виде ориентированных графа, где вершинами являются состояниями, возможные переходы между ними — ребрами, причем начало ребра помечено символом, который должен быть на ленте для активации перехода, а конец ребра помечен символом, который пишется на ленту, и командой перемещения головки («L», «R», «_» ):

ПРИМЕР:

Условие:

Для слова babaaa : а) Построить граф переходов машины Тьюринга

 

б) Составить протокол работы машины Тьюринга.

 

Решение:

 

а) Граф переходов

 

б) Протокол работы:

 

Вопрос 34

Понятие вычисления на машине Тьюринга. Вычисление арифметических функций на МТ.

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

МТ вычисляет функцию . Если каковы бы не были числа существует такой момент времени в котором:

1. МТ достигает заключительного состояния ;

2. На ленте будет представлена система из n+1 числа, где , х- рез-т , который машина воспринимает в стандартном положении.

3. Все ячейки расположенные правее управляющей головки пусты.

Рассмотрим МТ вычисление элементарные арифметические функции:

• Машина обращается к след числу :

• Для обращения к предыдущему числу:

• Машина для функции непосредственного следования:

• Машина для организации циклов (для конечного числа): в скобках

Т-будет пониматься любая машина , которую необходимо зациклить.

• Таблица для перемножения чисел: н-р 011..1011..10 в рез-те получим 011..1011..1011..10

Восновуположентакойалгоритм : S:=0; for i:= 1 to do; for j:= 1 to do; S:=S+1;

mul(вложенность) –внешний цикл ;-внутренний цикл;

Теорема Тьюринга. Для каждой частично рекурсивной словарной функции определенной в некотором алфавитесуществует МТ с символами

Оценка сложности по отношению к МТ :

МТ используется как критерий для установления разрешимости или не разрешимости проблемы.