Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Пример 10.4

Машината на Тюринг е формална система, която генерира много от своите конфигурации. Изходният обект е началната конфигурация; правила - функционална таблица. Въпреки това по-рано (гл. 7) беше доказана еквивалентността на представянето на алгоритми в различни алгоритмични модели. Следователно, ако алгоритъмът в представянето на машината на Тюринг е формална система, тогава алгоритъмът във всяко друго представяне също се оказва формална система. В същото време обратното твърдение (“всяка формална система е алгоритъм”) ще бъде неправилно - причината за това обстоятелство ще стане по-ясна при обсъждането на свойствата на формалните системи.

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

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

2) Формалност. Същността на формалния подход е да се изпълнят (спазват) редица принципи:

· Принцип на педантичност: всичко, което се прави, се извършва строго според правилата на формалната система. Ако формалната система не позволява изграждането на желаните обекти в рамките на съществуващите правила, тогава е невъзможно да се изгради, нарушавайки правилата. Можете да промените съществуващите правила или да въведете нови, но това е равносилно на изграждането на друга формална система;

· Принципът на изричното описание: изрично са посочени всички условия за прилагане на правилата и действията, които трябва да бъдат изпълнени при прилагането им. Формулировката и описанието на действията не трябва да използват знанията и опита на изпълнителя или „действието по подразбиране“, т.е. нещо, което не е изрично описано, но подразбиращо се. На практика, за да се изгради такова строго описание, ако успее, то се оказва много тромаво. Обаче, да се провежда стриктно и последователно се оказва незадължително: ако изпълнителят е човек, първо можете да му предадете необходимите знания и след това да разчитате на тях; ако изпълнителят е устройство, детайлът на описанието се определя от съществуващата система от команди.

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

3) Елементарно действие. Въпросът е, че въпреки че правилата на една формална система могат да имат най-разнообразни форми, обаче, всяко сложно правило може да се сведе до поредица от прости комбинаторни манипулации с елементи от системата, които са от механичен характер. В теорията на алгоритмите тези манипулации вече са обсъждани; когато се прилага към формални системи, това генерира следния набор от елементарни действия:

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

· Замяна на един елемент с друг (или група от други);

· Изтриване на елемент (т.е. неговото заместване с празен елемент).

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

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

По отношение на разглежданите общи свойства на формалните системи е необходимо да се направят още няколко забележки.

Формалната система функционира строго според своите правила и разграничава обектите си само от синтактични характеристики. От тази гледна точка, тя уникално определя определен математически модел. Но когато се използва този модел за решаване на някакъв проблем, специфичните свойства и характеристики се присвояват на елементите на формалната система, т.е. системата се интерпретира . Подобен механизъм е широко използван в програмирането: разработена е процедура, която осигурява изпълнението на определена поредица от действия за обработка на данни с формални параметри (т.е. определена схема, последователност на обработка) и след това при извикване на процедура вместо формални се извършва подмяна на действителните стойности. Същата формална система може да има различни интерпретации, в зависимост от тематичната област, в която се използва моделът, или от целите, за които е създаден. Например, за формална система, описваща законите на математическата логика, има различно тълкуване - правилата за функционирането на логическите схеми, което беше обсъдено по-рано.

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





Вижте също:

Пример 9.2.

Сложност на алгоритъма

Пример 2.3

Пример 4.15

Глава 8. Формализиране на представянето на алгоритми

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru