Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

Согласно теореме Тьюринга, существует машина Тьюринга Т, имею­ щая внешний алфавит ао, A (а и — новый, не входящий в А символ), и вычисляющая функция F(p).

Пусть qo, qi, ..., qn — внутренние состояния Т и П — программа подстановок для машины Т. Заменяя входящие в П формулы вида

б) рассмотреть на нем примеры дедуктивных цепочек, задавая исходное слово длиною неменее трех символов.

2.Задать нормальный алгоритм Маркова, реализующий вычи­ тание А—В, где значениями А и В являются натуральные числа, представленные строками, состоящими из символов 1 (например, для А = 4 , 5 = 3, А — В= 1 слово '1111—111' должно быть пере­ работано алгоритмом в слово Т ) .

Проверить работу алгоритма для случаев: а) А = 6, В = 2; б) А = 3, В = 5.

3.Нормальный алгоритм Маркова, реализующий операцию ум­

4. Задать нормальный алгоритм Маркова, реализующий опера­ цию умножения чисел, представленных в виде последовательности единиц (алгоритм должен быть отличен от алгоритма п. 3). По­ строить дедуктивную цепочку для одного из входных слов.

5. Задать нормальный алгоритм, реализующий операцию срав­ нения призначной части двух чисел, заданных в виде:

В пунктах а и б призначная часть числа представлена символа­ ми V , а в пункте в она представлена в тех же символах, что и само число, т. е. единицами.

52

Построить соответствующие дедуктивные цепочки по каждому алгоритму.

6. Выполнить суперпозицию нормальных алгоритмов, получен­ ных в пп. 3 и 4.

Построить дедуктивную цепочку для одного произвольного при­ мера.

1.5.Операторные алгоритмические системы

1.5.1.Общие замечания

Одной из особенностей абстрактной теории алгоритмов являет-- ся неизменность набора допустимых средств, используемых для построения записи алгоритма или при его выполнении. Например, все частично рекурсивные функции получаются из некоторого фик­ сированного набора базисных функций с помощью трех операто­ ров — оператора"подстановки, оператора примитивной рекурсии, оператора наименьшего корня.

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

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

ее переработки выбирались в зависимости от класса рассматривае­ мых алгоритмов.

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

В то же время допущение формирования команд алгоритма в процессе ее реализации приводит к существенному сокращению и упрощению записи алгоритма. В связи с этим следующим требо­ ванием, предъявляемым к понятию алгоритма, является допуще­ ние формирования команд алгоритма в процессе его выполнения.

S3.

Рассмотрение реальных алгоритмов показывает, что все элемен­ тарные операции, производимые в процессе выполнения алгорит­ мов, распадаются на две группы операций, которые обычно назы­ вают арифметическими и логическими. Арифметические операции осуществляют непосредственное преобразование информации. Ло­ гические операции*определяют дальнейшее направление счета, т. е. последовательность выполнения арифметических операций. При этом во многих сложных алгоритмах преобладают логические опе­ рации, в то время как преобразование информации носит иногда •очень простой характер. К числу таких задач относится и большин­ ство экономических задач.

Элементарные акты, аналогичные логическим операциям, в яв­ ном или неявном виде вводятся и при определении понятия выпол­ нения алгоритма в абстрактной теории алгоритмов.

Например, при выполнении нормального алгоритма после рас­ смотрения очередной формулы подстановки осуществляется либо переход к следующей формуле подстановки, либо остановка, либо переход к первой формуле подстановки схемы алгоритма.

В машине Тьюринга логической операцией можно^ считать дви­ жение ленты вправо или влево в зависимости от состояния машины и прочитанного символа. .

Однако, как правило, логические операции в классических алго­ ритмических системах носят тривиальный характер. Во многих слу­ чаях такая тривиальность логических операций сильно усложняет построение конкретных алгоритмов.

В связи с этим следующим требованием, которое предъявляется к определению алгоритма, является допущение более универсаль­ ных логических элементарных операций, нежели те, которые имеют­ ся в абстрактной теории алгоритмов.

В той или иной мере этим требованиям отвечают так называе­ мые операторные алгоритмические системы, к рассмотрению кото­ рых мы и переходим.

1.5.2. Операторные алгоритмы Ван Хао

Операторный алгоритм Ван Хао задается последовательностью приказов специального вида. Каждый приказ имеет определенный номер и содержит указания': какую операцию следует выполнить над заданным объектом и приказ с каким номером следует далее выполнить над результатом данной операции. Общий вид такого приказа:

54

получим число 4 и указание выполнять далее над 4 приказ с номе­ ром?. Выполнив этот приказ над числом 23, получим снова число 23 и указание выполнять над 23 приказ с номером 13.

Заключительному состоянию машины Тьюринга в операторных алгоритмах соответствует приказ вида

стоп

который означает, что вычисления следует остановить. Число, над которым следует выполнить этот приказ, есть результат вычисле­ ний.

будет пара чисел [сог(х), а,]. Если а>(х) не определено, то результа­

55

i + n — 1 — шаг. Если в качестве результата на данном шаге полу­ чится пара, указывающая на заключительный оператор (z, i + n),

торный алгоритм А с программой (х) вычисляет частичную функцию

работки х согласно программе (12) должен быть бесконечным. Природа функций, вычислимых посредством операторных алго­

ритмов Ван-Хао, зависит от того, какие функции coi входят в записи приказов. Имеет место следующая теорема, определяющая приро­ ду фуНКЦИЙ COi.

Теорема (3). Для того чтобы частичная функция f(x) была вы­ числимой с помощью операторного алгоритма, программа которо­ го содержит лишь частично рекурсивные функции u>i{x) с рекурсив­ ной областью определенности, необходимо и достаточно, чтобы f (х) была частично рекурсивной.

Необходимость условий очевидна, и мы ограничимся лишь до­ казательством их достаточности.

Прежде всего введем понятие одной важной для доказательст­ ва функции. Эту функцию будем обозначать через ех (х, у) или со­ кращенно ехху и называть экспонентой числа рх в числе у. При

56