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

Проблем на алгоритмичната разрешимост

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

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

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

Първите доказателства за алгоритмична неразрешимост са свързани с някои въпроси на логиката и самата теория на алгоритмите. Оказа се, например, че проблемът за установяване на истинността на произволна формула на предикалното смятане (т.е. предикатното смятане е неразрешимо) е неразрешима - тази теорема е доказана през 1936 година. Чрез Църква.

През 1946-47 АА Марков и Е. Пост независимо доказаха отсъствието на алгоритъм за разпознаване на еквивалентността на думата в всяко асоциативно изчисление.

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

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





Вижте също:

Условна ентропия

Вероятността на който и да е от двата резултата от независими и несъвместими събития е равна на сумата на техните вероятности.

А.1. Понятие за вероятност

Ентропията на сложен експеримент, състоящ се от няколко независими, е равна на сумата на ентропията на отделните експерименти.

Пример 7.7

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

2019 @ ailback.ru