Черч тезисі.
Алгоритмдік – есептелетін бөлшекті сандық функциялар класы барлық бөлшекті рекурсивті функциялар класымен беттеседі.
Бөлшекті рекурсивті функция ұғымы есептелетін бөлшекті функция интуитивті ұғымының ғылымы эквиваленті бола алады.
Рекурсивті функция ұғымы қатаң. Сондықтан кәдімгі математикалық техника есепті шешетін функция рекурсивті болуы мүмкін емес деп дәлелдейді.
Интуитивті есептелетін функция ұғымы қатаң емес математикалық ұғым. Бірақ ол бөлшекті рекурсивті функция – қатаң математикалық ұғыммен байланысады.
79. Мәліметтер әдісі алгоритмдік шешімін дәлелдеу әдісі ретінде не мағына береді және салыстырмалы талдау жасаңыз.
Әдетте, жаңа есептердің шешілмеуі белгілі алгоритмдік шешілмейтін есептерді осы есептерге дейін азайту арқылы дәлелденеді. Осылайша, егер жаңа тапсырма шешілсе, онда әдейі шешілмейтін мәселені шешуге болатындығы дәлелденді. Араластыру әдісін қолдана отырып, олар әдетте өзін-өзі қызықтырмайтын, бірақ жоғарыда сипатталған мәселе сияқты олардың шешілмейтіндігін тікелей дәлелдеу оңай болатын жасанды тапсырмаларға сілтеме жасайды
80. Тьюринг машинасында орындалатын командаларды атап, мысал келтіріңіз.
Тьюринг машинасы екі бағытта да шексіз, ұяшықтарға бөлінген таспадан және бағдарламамен басқарылатын автоматтан (бас) тұрады.
Тьюринг машиналарына арналған бағдарламалар кесте түрінде жазылады, мұнда бірінші баған мен жолда сыртқы алфавиттің әріптері және автоматтың мүмкін болатын ішкі күйлері (ішкі алфавит) болады. Кестенің мазмұны Тьюринг машинасына арналған командалар. Басшының ұяшықта оқитын әріпі (қазіргі уақытта оның үстінде орналасқан) және бастың ішкі күйі қандай пәрменді орындау керектігін анықтайды. Команда кестедегі сыртқы және ішкі алфавиттердің таңбаларының қиылысуымен анықталады.
Белгілі бір Тьюринг машинасын анықтау үшін оның келесі компоненттерін сипаттау қажет:
Сыртқы алфавит.Ақырлы жиын (мысалы, А), оның элементтері әріптер (таңбалар) деп аталады. Бұл алфавиттің әріптерінің бірі (мысалы, 0) бос таңба болуы керек.
Ішкі алфавит.Бас (автомат) күйлерінің ақырлы жиыны. Күйлердің бірі (мысалы, q 1) бастапқы болуы керек (бағдарламаны іске қосу). Күйлердің екіншісі (q 0) түпкілікті болуы керек (бағдарламаны аяқтау) - тоқтату күйі.
Үстелге секіру.Машинаның (бастың) күйіне және оқылған сипатына байланысты мінез-құлқын сипаттау.
Достарыңызбен бөлісу: |
