 |
Есептелетін функциялар
|
|
|
|
натурал сандар жиынында берілген немесе оның ішкі жиыныда берілген және N жиынынан мәндер қабылдайтын, бір аргументке немесе бірнеше аргументке тәуелді 
функциясын қарастырамыз.
1 анықтама. 
функциясы есептелімді деп аталады, егер оның барлық аргументтерінің мәндерін есептейтін және тоқтаусыз жұмыс жасайтын алгоритм табылса.
болсын.
2 анықтама. Егер кез келген элемент берілген М жиынына тиісті ме, жоқ па екенін анықтайтын алгоритм тбар болса, онда М жиыны шешілімді жиын деп аталады.
Егер 
функциясы М жиыныда берілсе және {0,1} екі элементті жиыннан мәндер қабылдаса, онда функциясы М жиынының сипаттамалық функциясы деп аталады және келесі түрде анықталады:
М жиыны шешілімді ó егер оның сипаттамалық функциясы есептелімді болса.
3 анықтама. М 
N жиыны саналамды (рекурсивті немесе алгоритмді) деп аталады, егер М жиыны немесе бос жиын болса немесе оның мәндер жиыны қандай да бір есептелімді функция болса, басқаша айтқанда оның барлық элементтерін тізбектеп табатын алгоритм табылса.
Мысал. М={1,4,9,…..} натурал сандардың квадраттары жиынын қарастырамыз. Ол 1,2,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 бет
Бақылау сұрақтары:
1. Алгоритм түсінігін беріңіз.
2. Қандай функция есептелінетін деп аталады?
3. Қандай жиын шешілімді деп аталады?
4. Тьюринг машинасының сипаттамасын беріңіз.
|
|
|
