Дәрістер тезистері 1 тақырып Жиындар теориясының элементтері Мақсаты
жүктеу/скачать 2,49 Mb.
|
- Бұл бет үшін навигация:
- Әдебиет
| 3 Тьюринг машинасы
Бұл түсінік ағылшын математигінің атымен аталған, алғаш рет 1937 жылы, бірінші ЭЕМ пайда болғанға дейін 9 жыл бұрын берілген. Тьюринг машинасының анықтамасы Тьюринг машинасы кәдімгі машина емес, математикалық (елестететін) машина. Бұл функция, туынды, интеграл және т.с.с. математикалық объектілер. Басқа да математикалық түсініктер сияқты, Тьюринг машинасы да кейбір нақты процестердің модельдерін жасайды. Тьюрин машинасын автоматты жұмыс істейтін қондырғы түрінде көрсету ыңғайлы. Әрбір дискретті кезеңде қондырғы қандай да бір күйде бір ұяшықтың қрамын лента арқылы қарап шығып, бір қадам жасайды. Жаңа қадам жасаған кезде қаралатын ұяшықтың құрамын сол жақтан және оң жақтан өзгертіп, басқа күйге түседі. Әрбір қадам берілген команда бойынша жүзеге асады. Барлық командалар жиынтығы Тьюринг машинасының программасын көрсетеді. Тьюринг машинасының сипаттамасы. - Тьюринг машинасының белгіленуі. Тьюринг машинасы - сыртқы алфавит деп аталатын және осы алфавит құратын ақырлы белгілерден тұрады. лентасының әрбір ұяшығына, әрбір ақырлы уақытта А алфавиттен бір ғана символ жазылады. А алфавитте «бос әріп» бар деп есептейміз және ол бос ұяшықта жазылған болсын. «Бос әріп» немесе бос ұяшықтың символы деп белгіленсін. Лента екі жағынан да шектелмеген деп ұйғарылады, бірақ әрбір уақыт кезеңінде оған бос емес әріптердің ақырлы саны жазылады. Әрбір уақыт кезеңінде машинасы ақырлы ішкі күйлердің бірінде болады, - ішкі күйлер жиынтығы болсын. Олардың арасында - бастапқы күйі, ал қорытынды немесе тоқтау кезеңіндегі күйі. жағдайында машина жұмыс істеуді бастайды, ал жағдайында машина тоқтайды. Тьюринг машинасының жұмысы программамен (функционалды схемамен) анықталады. Программа командалардан тұрады. Әрбір команда T (I , j) ( I =1,2,…m; j=0,1,….n) келесі өрнектердің бірі болып табылады. 1 өрнегіндегі С символы көбіне жазылмайды. ; Тьюринг машинасының жұмысы. Қандай да бір уақыт кезеңінде ( жағдайынан басқа кезде) машина оның және лентадағы символы арқылы қадам жасайды. Қадамның мазмұны: T( I , j ): командасына сәйкес, мұндағы . командасы бойынша, машина qi жағдайында әрпі жазылған ұяшықты қарайды, содан кейін машина жағдайына ауысады, қаралған ұяшықты әрпін өшіріп, онда әрпін енгізеді. Х=П, Х=Л байланысты машина оң жақ, немесе сол жақ ұяшықты қарастырады. Егер ештеме жазылмаса, сол ұяшықты қарайды. Осы командаларды орындағаннан кейін, машина qkal→qras орындайды, т.с.с. Әдебиет: 17, 254 бет,6,209-226 бет Бақылау сұрақтары: Алгоритм түсінігін беріңіз. 2. Қандай функция есептелінетін деп аталады? 3. Қандай жиын шешілімді деп аталады? 4. Тьюринг машинасының сипаттамасын беріңіз. жүктеу/скачать 2,49 Mb. Достарыңызбен бөлісу:
|