Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

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

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

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

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

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

A0 , A1 , A2 , …, An,…

 

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

B0 , B1 , B2 , …, Bm,…

 

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

 

m=j(n) (3.9)

 

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

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

 

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

 

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

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

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

 

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

 

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

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

 

60=22 31 51 , т.е. a 1=2, a 2=1, a 3=1.

 

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

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

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

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

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

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

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

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

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

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

 

a1 , a2 , …, ai, …,

 

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

 

b1 , b2 , …, bj, ….

 

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

j = jk (i). (3.12)

 

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

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

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

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

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

Действие машины Тьюринга однозначно определяется исходным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через S i (S 0=0, S 1=l) символ, считываемый головкой, через R J (R 0 – стоп, R 1 - влево, R 2 - вправо) - команду на перемещение головки и через qk (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 0 (стоп) и автомат остается в состоянии покоя q *. Придя в состояние q *, автомат заканчивает выполнение алгоритма, и дальнейшая работа машины Тьюринга прекращается.

Таблица 3.3

Состояние Вход
  S 0= 0 S 1= 1
q 1 q 2 q 3 S 0, R 2 , q k S 1, R 0, q s S 1, R 1, q p S 1, R 1, q m S 0, R 1, q l S 0, R 2, q s

 

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

 

Таблица 3.4

Q S
  0 1
q * q 1 0, R 0, q * 1, R 0, q *   1, R 0, q * 1, R 2, q 1  

 

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

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

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







Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

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

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...





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


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.