Реферат: Формализация понятия "алгоритм"

2) строки кодовых записей должны однозначно разбиваться на отдельные кодовые группы;

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

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

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

Пусть заданы машины Тьюринга 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.

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