Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

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

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

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

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

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

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 × … pm-1a m (3.11)

 

где p0=2, p1=3, p2=5, и вообще pm-1 - m-е простое число.

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

 

60=22 31 51 , т.е. a1=2, a2=1, a3=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 команды, под влиянием которых она может заменить символ, записанный в ячейке, над которой она находится.

Действие машины Тьюринга однозначно определяется исходным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через Si (S0=0, S1=l) символ, считываемый головкой, через RJ (R0 – стоп, R1 - влево, R2 - вправо) - команду на перемещение головки и через qk (k=1,2, … , n) - состояние управляющего автомата. Тог­да его таблица переходов может быть представлена таким образом (табл. 3.3).

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

Таблица 3.3

Состояние Вход
  S0=0 S1=1
q1 q2 q3 S0 , R2 , qk S1 , R0, qs S1 , R1, qp S1 , R1, qm S0 , R1, ql S0 , R2, qs

 

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

 

Таблица 3.4

Q S
  0 1
q* q1 0, R0, q* 1, R0, q*   1, R0, q* 1, R2, q1  

 

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

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

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









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


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