Формализиране на понятието "алгоритъм"

ФОРМАЛИЗИРАНЕ НА КОНЦЕПЦИЯТА НА "АЛГОРИТЪМА"

1.1. ФОРМУЛИРАНЕ НА ПРОБЛЕМА

Понятието алгоритъм, представено в предишния раздел, може да се нарече алгоритъм в интуитивен смисъл. Той има неясен, неформален характер, отнася се до някои не точно определени, но интуитивни неща. Например, когато дефинирахме и обсъждахме свойствата на алгоритъма, изхождахме от възможностите на определен изпълнител на алгоритъма. Присъствието му се предполагаше, но за него не се знаеше нищо категорично. Говорейки на езика на математиката, ние не сме дали нито аксиоматично, нито изчерпателно конструктивно определение на изпълнител.

Свойствата на алгоритмите, установени в предишния раздел, трябва да се нарекат емпирични. Те се разкриват въз основа на обобщаване на свойствата на алгоритмите от различно естество и имат приложен характер. Тези свойства са достатъчни за практическо програмиране, за създаване на широк спектър от програми за компютри, CNC машини, индустриални роботи и др. Като фундаментална научна концепция обаче алгоритъмът изисква по-подробно проучване. Невъзможно е без изясняване на понятието "алгоритъм", по-строго описание на него или, както се казва, без да се формализира.

Има няколко подхода за формализиране на понятието "алгоритъм":

• теория на крайни и безкрайни автомати;

• теория на изчислимите (рекурсивни) функции;

Всички тези подходи, възникнали исторически независимо един от друг, се оказаха впоследствие равностойни. Основната цел на формализирането на понятието алгоритъм е следната: да се подходи към решението на задачата за алгоритмична разрешимост на различни математически задачи, т.е. да отговори на въпроса дали може да се изгради алгоритъм, който да води до решението на проблема. Ще разгледаме формулирането на този проблем и някои резултати от теорията на алгоритмичната разрешимост на проблемите, но първо ще обсъдим формализирането на концепцията за алгоритъм в теорията на автоматите на примера на машини на Пост и Тюринг, както и нормални алгоритми на Марков, а след това - основите на теорията на рекурсивните функции. Идеите за λ-смятане на Църквата са реализирани в езика за програмиране LISP (Глава 3).

В същото време алгоритъм, формално дефиниран от някой от известните методи, не може да замени в практическото програмиране това, което наричахме алгоритми в предишния раздел. Основната причина е, че официалната дефиниция рязко стеснява обхвата на разглежданите проблеми, което прави много практически важни проблеми недостъпни за разглеждане.

1.2. ПОЩ МАШИНА

Абстрактни (т.е. съществуващи не всъщност, а само във въображението) машини Post и Turing, предназначени да докажат различни твърдения за свойствата на програмите за тях, бяха предложени независимо една от друга (и почти едновременно) през 1936 г. от американския математик Емил Пост и английският математик Алън Тюринг. Тези машини са универсални изпълнители, които са напълно детерминирани, позволявайки ви да „въведете“ първоначалните данни и след изпълнението на програмите да „прочетете“ резултата. Пощенската машина е по-малко популярна, въпреки че е много по-проста от машината на Тюринг. С негова помощ можете да научите първите умения за съставяне на компютърни програми.

Абстрактната машина на Post е безкрайна лента, разделена на еднакви клетки, всяка от които може да бъде празна или запълнена с знак „V“, а глава, която може да се движи по лентата с един квадрат надясно или наляво, може да бъде маркирана в лентата квадрат, ако тази марка не е била там преди, изтрийте марката, ако е била, или проверете за наличие на марка в клетката. Информацията за запълнените клетки на лентата характеризира състоянието на лентата, което може да се промени по време на работата на машината. Във всеки момент от времето главата („-“) е над една от клетките на лентата и, както се казва, я изследва. Информация за местоположението на главата заедно със състоянието на лентата характеризира състоянието на пощенската машина, фиг. 1.16.

Фигура 1.16. Публикувайте абстрактна машина

Командата Post machine има следната структура:

където n е поредният номер на командата, K е действието, извършено от главата, m е номерът на следващата команда, която трябва да бъде изпълнена.

Има общо шест команди на машината за поща, Фигура 1.17:

Фигура 1.1. Команди за пощенски машини.

Ситуациите, при които главата трябва да постави знак там, където вече съществува, или, обратно, да изтрие знак там, където не съществува, са извънредни (неприемливи).

Програма за пощенска машина е непразен списък от команди, така че 1) на n-то място е командата с номер n; 2) числото m на всеки отбор съвпада с номера на която и да е команда в списъка.

От гледна точка на свойствата на алгоритмите, изследвани с помощта на машината Post, причините за спирането на машината по време на изпълнението на програмата представляват най-голям интерес:

1) спиране по команда "стоп"; такова спиране се нарича ефективно и показва коректността на алгоритъма (програмата);

2) спиране при изпълнение на невалидна команда; в този случай спирането се нарича неефективно;

3) колата никога не спира; в този и в предишния случай имаме работа с неправилен алгоритъм (програма).

Ще разберем от първоначалното състояние на главата срещу празна клетка вляво от най-левия етикет на лентата. Помислете за изпълнението на някои типични елементи от програмите на Post machine.

1. Нека бъде дадено първоначалното състояние на главата и се изисква да напишете два етикета на празна лента: един в раздела под главата, вторият вдясно от него. Това може да стане с помощта на следната програма (резултатът от нейното изпълнение е показан вдясно от командата):

Фигура 1.2. Пример за програмен елемент на пощенска машина.

2. Нека покажем как можете да използвате командата за условен клон, за да организирате цикличен процес. Да предположим, че лентата съдържа запис от няколко знака подред и главата е разположена над най-крайния знак вдясно. Необходимо е да преместите главата наляво в първата празна позиция.

Програмата ще изглежда така:

Командата за условен скок е един от основните инструменти за организиране на циклични процеси, например за намиране на първия етикет вдясно (или вляво) на главата, разположен над празна клетка; да е вляво (или вдясно) от главата на празна клетка, ако тя се намира над етикета и т.н.

3. Нека се спрем на представянето на числата на лентата на Пощенската машина и извършването на операции върху тях.

Числото k е представено на лентата на пощенската машина чрез последователни k + 1 етикета (един етикет означава числото "O"). Интервал от поне един празен участък на лентата се прави между две числа. Например, записването на числата 3 и 5 на лентата на пощенската машина ще изглежда така:

Имайте предвид, че системата за писане на числа, използвана в машината на Post, не е позиционна.

Нека съставим програма за добавяне на единици към произволно число. Да предположим, че на лентата има само едно число, а главата е над една от клетките, съдържаща етикета, принадлежащ на този номер:

За да разрешите проблема, можете да преместите главата наляво (или надясно) до първата празна клетка и след това да приложите знак.

Програмата, която добавя етикет вляво от номера, изглежда така:

Програмата, която добавя етикет вдясно към номера, изглежда така:

(разликата е само в посоката на движение на главата при първата команда. Проверете работата на тези програми на конкретни примери).

Да предположим, че главата е разположена на няколко клетки вляво от номера, към който искате да добавите една. В този случай програмата става по-сложна. Ще се появи "блок за търсене на числа" - две команди, които водят главата до състоянието, разгледано в предишния пример:

По-долу са пълните текстове на програмите, добавящи единица съответно отляво и отдясно:

В първия случай не е нужно да премествате главата до най-левия етикет на номера

4. Нека представим програма за добавяне на неотрицателни цели числа a и u на пощенска машина, когато главата е над числото a, а числото b е вдясно от числото a от определен брой клетки. Тази програма изпълнява следния алгоритъм: първото число постепенно се премества към второто, докато се слеят, а след това един етикет се изтрива (в противен случай резултатът би бил с един повече от правилния).

В случай на по-сложни начални условия, когато не е известно дали числото е отдясно или отляво на главата (и от какъв брой клетки), може да се приложи следният принцип за намиране на число: чрез преместване главата надясно и наляво и маркиране на степента на отстраняване на главата от първоначалното положение, намерете номера и след това приложете добре познатата програма за добавяне. Това проверява дали главата е над един от етикетите с номера и ако е така, тогава проблемът е решен. В противен случай се проверява дали участъкът вдясно от главата и следващият след него са празни; ако и двете са празни, тогава главата се връща с една стъпка и се поставя марка, след което се извършва същата операция вляво и главата се връща вдясно по маркираната писта и т.н. докато главата удари число, след което могат да се приложат предварително обсъдените програми:

Машината на Post може да се разглежда като опростен компютърен модел. Всъщност и компютърът, и машината на Post имат:

• неделими носители на информация (клетки - битове), които могат да бъдат запълнени или незапълнени;

• ограничен набор от елементарни действия - команди, всяка от които

изпълнява се в един цикъл (стъпка).

1.3. ТУРИНГ МАШИНА

Машината на Тюринг е подобна на машината Post, но функционира малко по-различно.

Машината на Тюринг (MT) се състои от преброяваща лента (разделена на клетки и ограничена отляво, но не и отдясно), глава за четене и запис, лентово задвижване и оперативен задвижващ механизъм, който може да бъде в една от дискретни състояния qo, q1. qs, принадлежащи към някаква крайна колекция (азбуката на вътрешните състояния). Освен това qо се нарича начално състояние.

Редът на работа на МТ (с работеща азбука a0, a1. Аt и състояния q0, q1. Qs) е описан от таблицата на машината на Тюринг. Тази таблица е матрица с четири колони с (s + 1) (t + 1) редове. Всеки ред има формата

Тук vij означава елемента на комбиниране на азбуката и набор от инструкции за лентовия механизъм: l - преместване на лентата наляво, r - преместване на лентата надясно, s - спиране на машината; vij - действието на MT, състоящо се или от въвеждане на символа на азбуката a0, a1 в лентовата клетка. при, или при движение на главата, или при спиране на машината; qij е последващото състояние.

MT работи съгласно следните правила: ако MT е в състояние qi, главата чете символа 0 в работната клетка. Нека низът qi аj vij qij, започвайки със символи qi, aj, се появи само веднъж в таблицата. Ако vij е буква от работещата азбука, тогава главата изтрива съдържанието на работната клетка и поставя тази буква там. Ако vij е команда r или l за лентово устройство, лентата се премества съответно с едно пространство надясно или наляво (ако не излиза извън левия край на лентата). Ако vij = s, тогава настъпва машинно спиране.

Машината на Тюринг започва от някаква първоначална конфигурация, включително първоначалното състояние (обикновено q0) и позицията на главата за четене-запис над определена лентова клетка, съдържаща един от символите на работещата азбука A.

Имайте предвид, че наличието на различни символи в работната азбука на МТ дава възможност да се представи произволен текст и цифрова информация на лентата, а преходите на контролния център на МТ към различни състояния симулират запаметяването на междинните резултати от работата на машината на Тюринг. Таблицата, която определя реда на работа на MT, в буквалния смисъл на думата не е програма (нейните инструкции не се изпълняват последователно, една след друга, а описват преобразуването на символи на някакъв текст на лентата). Таблицата МТ често се нарича схема на машината на Тюринг или просто се идентифицира със самата машина на Тюринг, тъй като нейната структура и принцип на работа са известни.

Помислете за примери на няколко схеми на машини на Тюринг.

1. Алгоритъм за добавяне на един към числото n в десетичната бройна система. Дава се десетична нотация на числото n (т.е. представянето на естественото число n в десетичната бройна система); изисква се да се получи десетичното представяне на числото n + 1.

Очевидно външната азбука MT трябва да се състои от десет цифри 0,1,2,3,4,5,6,7,8,9 и интервал _. Тези числа се записват едно по едно в клетка (в ред, без пропуски).

Оказва се достатъчно, за да има две вътрешни състояния на машината: q1 и q2.

Да предположим, че в началния момент главата е над една от цифрите на числото, а машината е в състояние q1. Тогава проблемът може да бъде решен на два етапа: преместване на главата до цифрата на числовите единици (във вътрешното състояние q1) и замяна на тази цифра с по-голяма (като се вземе предвид прехвърлянето на 1 към следващата цифра, ако е е 9, във вътрешното състояние q2. Съответната MT схема може да изглежда така