Главная Обратная связь

Дисциплины:






Алгоритмдік шешімі болу және болмау ұғымы туралы айт.



Алгоритмнің шешімі болу деп математикалық логикада формальды теорияның аксиомалар жиынынан осы теорияның қорытып шығарудың болу болмауының формуласын анықтайтын алгаритмнің бар екендігін білдіретін қасиетін айтады.

Теория шешілетін деп аталады егер осындай алгоритм бар болса керісінше жағдайда шешімі жоқ теория деп атайды.

Алгоритм ұғымы және аксиомалық жүйелер антикалық дәуірде белгілі болса (Евклид диаметриясы) шешімі болудың формальды анықтамасы тек XX ғасырдың басында іске асты. Алғашқы зерттеген Гильберт. Ол есептеу және нәтиеженің қалыптастырды ұғымдарды, оның мақсаты (математиканы формальдау болды математиканың кез келген формуласын шынайлыққа тексеру). Гильберт жұмысты басшылыққа ала отырып Гедел алғаш рекурсивті функция класын сипаттайды сол арқылы өзінің толық еместік теориясын дәлелдеді.Кейінен Тьюринг машинасы есептеу сияқты рекурсивті функция эквивалентті формализм енгізілді.Олардың әр қайсысы есептегі функция ұғымының формальды эквиваленті. Бұл эквиваленттік Черчтің тезисінде айтылады. Есептеу алгоритм ұғымы анықталған сон түрлі теорияның шешімі болмауы туралы нәтиежелер алынды. Солардың бірі Новиков теориясы. Ол топтағы сөздердің проблемасы шешімі болмау туралы айтады.

Ол топтағы сөздердің проблемасы шешілмейтіндігі туралы айтады.Ал, шешімі бар теория Шешілмейтін теория бұл күрделі теориядеген ұғымның синонимі.Теория неғұрлым күрделі болса, соғұрлым шешілмеуі мүмкін. Бұл жағдайда формальды есептеу тілді терминдер мен формуланы құру ережесін аксиома мен қорыту ережесіе анықтау тиіс.

Осылайша, Т - теоремасы үшін тібегін құруға болады.Мұндағы - не аксиома, не алдыңғы формуладан алыңған нәтиеже. Шешімі болу ұғымы: әрбір дұрыс құрылған Т- теория үшін шекті қадамнан соң бір мәнді түрде «ияә» (осы сөйлем есептеу шеңберінде қорытылып шығарылады) не «жоқ» (қорытылып шығарылмайды) алгоритмін болатындығын білдіреді.





sdamzavas.net - 2018 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...