Сведение любого алгоритма к численному алгоритму. Гёделизация

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

Уточняя понятие алгоритма, мы ввели в рассмотрение нормаль­ный алгоритм Маркова. Эта форма алгоритма удобна для специалиста-логика. Для тех же специалистов, которые имеют дело преимущест­венно с вычислительными машинами, безусловно важнее иметь разра­ботанный стандартный аппарат, более близкий к естественной форме численных алгоритмов.

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

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

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

Включим все условия задачи, доступные для переработки дан­ным алгоритмом А, в занумерованную неотрицательными целыми чис­лами последовательность

A₀ , A₁ , A₂ , …, A_n,…

Совершенно аналогично записи возможных решений также вклю­чим в занумерованную последовательность

B₀ , B₁ , B₂ , …, B_m,…

Как только проведена нумерация, становится очевидным, что любой алгоритм, перерабатывающий запись условий A_n в запись решения B_m, можно свести к вычислению значений некоторой числовой функции

m=j(n) (3.9)

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

Очевидно также, что если есть алгоритм, решающий исходную задачу, то есть и алгоритм вычисления значений соответствующей функции. Действительно, чтобы найти значение j(n) при n = п^*,можно по п^* восстановить запись условий задачи, затем с помощью имеющегося алгоритма найти запись решения и по записи решения определить номер m^*. Следовательно,

j(п^*)=m^*. (3.10)

Обратно, если есть алгоритм вычисления функции j(n), то, стало быть, имеется и алгоритм решения исходной задачи. Действи­тельно, по записи условий задачи можно найти соответствующий ей номер п^*, затем вычислить m^* = j(п^*) и по m^* определить запись решения.

Приведем теперь один широко применяющийся метод нумерации - метод Гёделя.

Рассмотрим запись некоторого числа n в форме

n = 2^{a 1} × 3^{a 2} × 5^{a 3} × 7^{a 4} × … p _m-1^{a m} (3.11)

где p ₀ =2, p ₁ =3, p ₂ =5, и вообще p _m-1 - m -е простое число.

Из этой записи видно (в силу теоремы о единственности раз­ложения любого числа на простые множители), что каждому числу n однозначно соответствует набор a ₁, a ₂, …, a _m и, наоборот, каж­дому набору a ₁, a ₂, …, a _m однозначно соответствует число n. Например, если n =60, имеем

60=2² 3¹ 5¹ , т.е. a ₁=2, a ₂=1, a ₃=1.

С помощью этого способа мы можем нумеровать теперь любые упорядоченные последовательности, состоящие из m чисел.

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

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

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

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

Машина Тьюринга

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

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

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

Представим совокупность всех возможных исходных данных, пе­рерабатываемых каким-либо алгоритмом А в виде последовательности

a₁ , a₂ , …, a_i, …,

а все возможные результаты - в виде последовательности

b₁ , b₂ , …, b_j, ….

Тогда любой алгоритм А_k, преобразующий исходные данные a_i в ре­зультат b_j, можно свести к вычислению функции j_k, указывающей номер результата j по номеру совокупности исходных данных i

j = j_k (i). (3.12)

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

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

Английский математик Тьюринг предложил абстрактную схему автомата, принципиально пригодного для реализации любого алго­ритма. Этот автомат, получивший название " Машина Тьюринга " явля­ется автоматом с бесконечной памятью.

Запоминающим устройством в машине Тьюринга служит лента. разделенная на ячейки №l, №2,... так, что эта лента имеет на­чало (ячейка №1), но не имеет конца (простирается в бесконеч­ность как последовательность натуральных чисел).

В каждой из ячеек может быть записан нуль или единица. Над лентой перемещается головка Т, управляемая автоматом L, обладаю­щим конечной памятью. Автомат L работает тактами. На его вход поступает информация о символе (0 или 1), считываемой головкой с ленты. Под влиянием команд, получаемых каждый такт от автомата L, головка может оставаться на месте или передвигаться на одну ячейку вправо или влево. Одновременно головка получает от авто­мата L команды, под влиянием которых она может заменить символ, записанный в ячейке, над которой она находится.

Действие машины Тьюринга однозначно определяется исходным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через S _i (S ₀=0, S ₁=l) символ, считываемый головкой, через R _J (R ₀ – стоп, R ₁ - влево, R ₂ - вправо) - команду на перемещение головки и через q_k (k =1,2, …, n) - состояние управляющего автомата. Тог­да его таблица переходов может быть представлена таким образом (табл. 3.3).

Как видно из табл. 3.3, действие автомата зависит от вхо­да S и его состояния q. Определенным значениям S _i и q _i соответс­твует определенная совокупность значений трех величин: S, R и q, обозначающих соответственно: какой символ S запишет головка на ленту, какова будет команда R на перемещение головки и в какое новое состояние q перейдет автомат L. Следует иметь в виду, что среди состояний q автомата L должно быть по крайней мере одно такое его состояние q ^*, при котором: головка не изменяет символа S, команда R=R ₀ (стоп) и автомат остается в состоянии покоя q ^*. Придя в состояние q ^*, автомат заканчивает выполнение алгоритма, и дальнейшая работа машины Тьюринга прекращается.

Таблица 3.3

Пусть, например, таблица перехода автомата L имеет следую­щий вид (табл. 3.4)

Таблица 3.4

Тогда, если в начальный момент автомат находится в состоя­нии q ₁, а головка расположена над ячейкой, в которой записан символ 1, то головка будет перемещаться вправо до тех пор, пока не обнаружит ячейку с символом 0, заменит его символом 1 и оста­новится. Если начальное состояние системы (состояние в нулевой такт) и заполнение ленты соответствуют показанным на рисунке "Машина Тьюринга", то, согласно табл. 3.4 система в последую­щие два такта перейдет в состояния, показанные на рис. 3.4, и на втором такте остановится.

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

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

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: