Информатика -продвинутый курс



         

. МАШИНА ТЬЮРИНГА - часть 5


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

Пусть заданы машины Тьюринга T1 и T2, имеющие общий внешний алфавит А = {a0, a1, ..., am} и внутренние состояния Q1 = {q0, q1,… qn} и Q2 = {q0, q1,

..., qt} соответственно. Композицией или произведением машины T1

и машины T2

будем называть машину Т с тем же внешним алфавитом А = {a0, а1, ...,

am} и набором внутренних состояний Q = {q0, q1,..., q2,, qn+1,..., qn+1} и программой, эквивалентной последовательному выполнению программ машин Т1

и Т2:

Т = T1 * T2..

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

c n сомножителями.

Операция итерации применима к одной машине и определяется следующим образом. Пусть машина T1

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

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




Содержание  Назад  Вперед