25.Моделдегі анықталымдылық.

а) Модел ұғымы.

в) Анықталымды қатынастар.

M = (M, Z) R ϵ Mⁿ; Егер φ( х₁,…..,х_n) R = {( a₁,…..,a­_n ) ◦ a ϵ Mⁿ және M ⃒= φ[a₁,…..,a_n]} x = 0 ⟺ R = { 0 } ϵ N; Z = ( S³, P³ ) R= { a: a ϵ M және M ⃒= ∀yS³(a, y, y)} x – жай сан ⟺ R = {2, 3, 5…} ϵ N; R = { p: p ϵ M және M ⃒= ∀y(y\p → y = ( y = p)) } 2 3 1 4 R = {(1;2); (2;1); (2;3); (3;2); (2;4); (4;2)} ∀a ϵ A => (a; a) ¢ R; ∀a, b ϵ A үшін (a, b) ϵ R => (b, a) ϵ R; (x = 0 ⟺ R = 0) 2 3 2 3 1 4 1 4

G₁ ᴜ G₂; G_{1 kiylysuy} G₂; G₁^-1 ; G_{1 *} G₂; G₁^-1 ;

a ≠ 0 <= { (0; 1); … , (0; a); … , (1; 2); … ; (2; 3); … , … }

20<= { (0; 2); … ; (1; 3); … } а) Модель (фр. modele, лат. modulus – өлшем) – белгілі бір зерттелетін нысанның ой түсінігі арқылы немесе материалдық түрде жасалған шартты үлгісі (бейнесі, сұлбасы, сипаттамасы, т.б.). Модель мен түп нұсқаны бір-бірінен абсолютті түрде айыруға болмайды. Қарастырылып отырған құбылыс немесе процесс абстрактылық нысандар мен математикалық заңдылықтар түрінде берілетін модель математикалық модель деп аталады. Модельдің ең қарапайым түрі нысандарды көрнекі етіп сурет, кескін, сызба формасында графиктік түрде көрсету. Модельдіңекінші түріне – нысандардың, процестер мен құбылыстардың ауызша (қандай да бір тілдің көмегімен) суреттелуі, сипатталуы жатады. Үшінші түрі –ақпараттық-логикалық модель, ауызша сипатталған нысанды кескіндеп көрсету (формалау). Төртінші түрі – динамиканың ішкі заңдарын, өзара әсерін, қасиеттерін көрсететін физикалық нысандардың, құбылыстар мен процестердің математикалық түрде сипатталуы Мысалы, белгілі бір физикалық процестің уақыт ішінде өтуін баяндайтын дифференциялдық теңдеулер жүйесі осы процестің моделі деп аталады. Модель ұғымы логика, математика, физика, химия, кибернетика, лингвистика, т.б. ғылым салаларында қолданылады. Ғылымда модель ұғымы әдетте модель жасау әдісін қолдануға байланысты аталады. Алгебра мен математика логиканың тоғысқан жеріндеарнаулы пән – модельдер теориясы қалыптастыру

27) Тъюринг машиналары.

а)Тъюринг машиналарының нұсқаулары.

в)Машиналық сөздер және оларды түрледіру.

1936 жылы Тъюринг кез келген есептеуді орындай алады деген жорамалмен теориялық машиналар класын енгізді. Олардың сипаттамасын берейік.

Көз алдымызға квадратттарға белінген ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын S₀, S₁,..., S_n символдары беріледі. Әр кезде әр квадратқа 6ip символ жазылады. Әр кезде квадратта 6ip символдан артық болмайды. Машинаның ішкі жагдайлары болып табылатын {q0,..., qm} жиыны болады. Әр кезде машина сол ішкі жагдайлардың біреуінде ғана болады. Сонымен бipгe кез келген уақытта квадраттардың бipeyiн ғана қарастыратын оку тетігі бар. Машина бip мезетте 6ip ғана қимыл істейді. Егер машинаның оқу тетігі қарастырылып турган квадратта S_i символы турса, ал машинаныц ішкі жагдайы q_j болса, онда ол келесі қимылдардың 6ipeyiн істейді:

Осы квадраттагы S_i символын emipin, S_j символын осы квадратка жазады;

Оң жақтагы көрші квадратка көшеді;

Сол жақтагы көрші квадратка көшеді;

Тоқтайды.

Алдыңғы үш жағдайда машина баска q_r ішкі жагдайға көшіп, келесі қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жок болса, онда керек квадрат пайда болады деп есептейміз.

Бос клеткада S₀ символы бар деп есептейік. Онда кез келген уакыт­та кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрьқ деп атайтын келесі реттелген төрттіктермен белгілеуге болады:

q_j S_i S_kq_r, (2) q_j S_i Lq_r, (3) q_j S_i Rq_r

Бұл жерде алдыңғы eкi символ - машинаның ішкі жагдайы мен қарастырылып отырған квадраттағы символ, үшіншісі - қандай символ жазылатындығының немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі қандай iшкі жағдайга көшетінін көрсетеді.

Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде кұрылган алгоритмді байланыстыра аламыз. Осы алфавиттегі кез келген сөзді солдан оңга қарай жазамыз. Оқу тетігі ең сол шеткі квадратты қарастырып турган кезде машина q₀ ішкі жагдайында жумысты бастайды. Әр кадамда не символ өшіріп, баска символ жазады, не көрші квадраттардың 6ipңне көшеді. Егер машина жумысын токтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюринг машинасының дәл аныктамасын берейік.

Келесі екі шартты канағаттандыратын акырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:

Төрттіктердің кез келгені не q_j S_i S_kq_r, не q_j S_i Lq_r, не ) q_j S_i Rq_r түрінде болады.

Алдыңғы eкi символдары бірдей болатын төрттіктер жок.

Әр төрттік бұйрық деп аталады. Бұйрьқтарға енетін S_m символдары сытркы жағдайлар деп аталады. Бұйрыктардагы q_s символдары ішкі жагдайлар деп аталады. q_Q кез келген машинаның ішкі жагдайы болып табылады.

28.Тъюринг машиналары.

а)Тъюринг машиналарының программалары.

в)Екі еселеу программасы.

Тьюринг машинасы

Әрине өткен параграфта қойылған сұрақтардың жауаптарын алгоритмнын дәл анықтамасы ретінде ала алмаймыз. 1936 жылы Тюринг кез келген есептеуді орындай алады деген жорамалмен теориялык машиналар класын енгізді. Олардың сипаттамасын берейік.Көз алдымызға квадратттарға бөлігінен ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын S 0, S1 ..., Sn символдары беріледі . Әр кезде әр квадратқа 6ip символ жазылады. Әр кезде квадратта 6ip символдан артык болмайды. Машинаның ішкі жағ дайлары болып табылатын {q0,..., qm} жиыны болады. Әр кезде машина сол iшкi жағдайлардың біреуінде ғана болады. Сонымен 6ipгe кез келген уақытта квадраттардың 6ipeyiн ғана қарастыратын оқу тетігі бар. Машина 6ip мезетте 6ip ғана қимыл шстейді . Егер машинаның оку тетігi қарастырылып турған квадратта . символы турса, ал машинаның ішкі жағдайыболса, онда ол келесі қимылдардың 6ipeyiн істейді:

1) Осы квадраттағы символын eшіріп,символын осы квадратқа жазады;

2) Оң жақтағы көpшi квадратқа көшеді.

3) Сол жақтағы көpшi квадратқа көшеді.

4) Токтайды.

Алдынғы уш жағдайда машина баска ішкі жағдайға көшіп, келесі қимылға дайын. Eкінші немесе үшінші қимыл кезінде көрші квадрат жок болса, онда керек квадрат пайда болады деп есептейміз. Бос клеткадасимволы бар деп есептейік. Онда кез келген уақытта кез келген клеткада символ бар. Алдынғы уш қимылды болашақта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:

(1 ), (2), (3)

Бұл жерде алдынғы eкi символ – машинаның ішкі жағдайы мен қарастырылып отырған квадраттағы символ, үшіншіci - қандай символ жазылатындығының немесе оңу тетігірің не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін көрсетеді.

Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді байланыстыра аламыз.Осы алфавиттегі кез келген сөзді солдан оңға карай жазамыз. Оқу тетігі ең сол шеткі квадратты карастырып турған кезде машина ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп,басқа символ жазады, не көрші квадраттардың 6ipінe көшедію Егер машина жұмысын токтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюринг машинасының дәл анықтамасын берейік.Келесі екі шартты канағаттандыратын ақырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:

1. төрттіктердің кез келген не , не, нетурінде болады.

2. Алдынғы eкi символдары бірдей болатын төрттіктер жок.

Әр төрттік бұйрық деп аталады. Бұйрыұтарға енетін Sm символдары сытрқы жағдайлар деп аталады. Бұйрықтардағы qs символдары ішкі жағдайлар деп аталады.кез келген машинаның iшкі жағдайы болып табылады.

29.Тъюринг машиналары.

а)Тъюринг машиналарының программалары.

в)Көшіру программасы.

Тьюринг машинасы

1936 жылы Тьюринг кез келген есептеуді орындай алады деген жорамалмен теориялық машиналар класын енгізді. Олардың сипаттамасын берейік.

Көз алдымызға квадраттарға бөлінген ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын S[0],S[1],...,S[n] символдары беріледі. Әр кезде әр квадратқа бір символ жазылады. Әр кезде квадратта бір символдан артық болмайды. Машинаның ішкі жағдайлары болып табылаын {q[0],...,q[m]} жиыны болады. Әр кезде машина сол іщкі жиындардың біреуінде болады. Сонымен бірге кез келген уақытта квадраттың біреуін ғана қарастыратын оқу тетігі бар. Машина бір мезетте ғана жұмыс істейді. Егер машинаның оқу тетігі қарастырылып тұрған квадратта S[i] символы тұрса, ал машинаның ішкі жағдайы q[j] болса, онда ол келесі қимылдардың біреуін істейді:

1. Осы квадраттағы S[i] символын өшіріп, S[j] символын осы квадратқа жазады;

2. Оң жақтағы көрші квадратқа көшеді; 3. Сол жақтағы көрші квадратқа көшеді;

4. Тоқтайды.

Алдыңғы үш жағдайда машина басқа q[r] ішкі жағдайға көшіп, келесі қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат пайда болады деп есептейміз. Бос клеткада S[0] символы бар деп есептейік. Онда кез келген уақытта кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:

1. q[j]S[i]S[k]q[r], 2. q[j]S[i]Lq[r], 3. q[j]S[i]Rq[r].

Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып отырған квадраттағы символб үшіншісі-қандай символ жазылғандығының немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін көрсетеді.

Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді баланыстыра аламыз. Осы алфавиттегі кез келген сөзді содан оңға қарай жазамыз. Оқу тетігенің ең сол шеткі квадратты қарастырып тұрған кезде машина q[0] ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп, басқа символ жазады, не көрші квадраттың біріне көшеді. Егер машина жұмысын тоқтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюринг машинасының дәл анықтамасын берейік. Келесі екі шартты қанағаттандыратын ақырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:

1. Төрттіктердің кез келгені не q[j]S[i]S[k]q[r], не q[j]S[i]L q[r], не q[j]S[i]Rq[r] түрінде болады.

2. Алдыңғы екі символдары бірдей болатын төрттіктер жоқ.

Әр төрттік бұйрық деп аталады. Бұйрық тарға енетін S[0] символдары сыртқы жағдайлары деп аталады. q[0] кез келген машинаның ішкі жағдайы болып табылады.