Əvvəlki paraqrafda “Verilmiş Turinq maşınının f(, ...,) funksiyasını necə qiymətləndirdiyinə” baxdıq. Bunun üçün, ... ədədlərinin hər birinin müvafiq ədədlərdən ibarət davamlı massivdə maşının lentinə yazılması və massivlərin özləri 0 simvolu ilə ayrılması lazımdır. f (, ...,) funksiyası verilmiş arqument qiymətləri toplusunda müəyyən edilir, nəticədə lentdə f (, ...,) vahidləri cərgəsinə yazılmalıdır. Eyni zamanda, biz deyildik. maşının hansı ilkin vəziyyətdə işə başlaması (çox vaxt bu standart ilkin mövqe idi), işi hansı vəziyyətdə bitirdiyi və bu işin necə getdiyi barədə çox ciddidir.
Bundan sonra, bir Turing maşınında funksiyanın hesablanması haqqında daha güclü bir anlayışa ehtiyacımız olacaq - düzgün hesablama anlayışı.
Tərif 5.1: Deyəcəyik ki, Tyurinq maşını 0 ... 0 ilkin sözünü 0 ... 0 sözünə çevirsə və eyni zamanda mətnə yeni xanalar əlavə etməsə, f (, ...,) funksiyasını düzgün hesablayır. lentdə ilkin söz ya sola, ya da sağa. Əgər f funksiyası verilmiş arqument qiymətləri dəstində müəyyən edilməmişdirsə, o zaman göstərilən mövqedən işə başladıqdan sonra iş zamanı heç vaxt sol tərəfdə lent qurmayacaqdır.
Misal 5.1. S(x) = x+1 və O(x) = 0 funksiyalarını düzgün qiymətləndirən Turing maşın proqramları bunlardır. S(x) = x+1 funksiyası tərcümə edir: 0 => . Onun proqramı: 0 > P, 1 > 1P, 0 > 1, 1 > 1L, 0 > 0. O(x) = 0 funksiyası tərcümə edir: 0 => . Onun proqramı belədir: 0 > 0P, 1 > 1P, 0 > 0L, 1 > 0, 0 > 0L, 0 > 0. Müvafiq Turinq maşını O təyin olundu.
Misal 5.2.İki avtomobil "sola sürüşmə" və "sağ sürüşmə" qurun. İlkin standart mövqedən birincisi 0 sözünü eyni sözə çevirir və sıfırla ən soldakı xanaya baxaraq dayanır. Sıfır olan sol xananın baxıldığı ilkin vəziyyətdən ikinci maşın 0 sözünü eyni sözə çevirir və ən sağdakı xananı sıfırla nəzərdən keçirərək dayanır.
Maşın proqramı: 0 > 0L, 1 > 1L, 0 > 0. Aydın olur ki, maşın proqramı əvvəlki maşının proqramından “L” simvolunu “P” simvolu ilə əvəz etməklə alınır.
Tyurinq maşınlarının tərkibi
Tərif 6.1:Ümumi xarici əlifbaya (, …,) və müvafiq olaraq daxili vəziyyətlərin (, …,) və (, …, ) əlifbalarına malik olan Turing maşınları və verilsin. Maşın üçün maşının tərkibi (və ya məhsulu) eyni xarici əlifbaya (, ...,), daxili əlifbaya (, ..., ..., ) malik olan yeni maşın və aşağıdakı kimi alınan proqramdır. Dayanma simvolunu ehtiva edən bütün əmrlərdə sonuncunu ilə əvəz edin. Komandalardakı bütün digər simvollar dəyişməz olaraq qalır. Əmrlərdə simvol dəyişməz qalır və bütün digər vəziyyətlər (i = 1, ..., t) müvafiq olaraq ilə əvəz olunur. Bu şəkildə alınan bütün əmrlərin məcmusu kompozisiya maşınının proqramını təşkil edir.
Təqdim olunan konsepsiya Turing maşınlarının layihələndirilməsi üçün əlverişli vasitədir. Bunu bir nümunə ilə göstərək.
Misal 6.1. Proyektor funksiyalarını (, …,) = (1? m ? n) düzgün hesablayan Turing maşınlarını quraq.
Əvvəlcə n=3, m=2 olan xüsusi halı nəzərdən keçirək, yəni. funksiyası (,) =. Biz 0 sözünü yenidən 0 sözünə çevirməliyik. İlkin konfiqurasiyaya əvvəllər qurulmuş Turing maşınlarını, B, O tətbiq edəcəyik:
Beləliklə, (,) = funksiyası maşınların aşağıdakı tərkibi ilə hesablanır: BOO = B.
İndi (, ...,) = formasının hər hansı bir funksiyasını hesablamaq üçün B, O maşınlarının tərkibinin qurulması alqoritmini təsəvvür edə bilərik. Düzgün sürüşmə ilə, m-1 dəfə tətbiq edərək, əvvəlcə sıraya çatmalısınız:
Sonra sola keçərək, massiv birinci yerdə olana qədər massivi sola bitişik olan hər massivlə köçürün (B istifadə edərək):
İndi (n-1) istifadə edərək, ən sağdakı sıraya çatmalısınız - sağ sürüşmənin çoxsaylı tətbiqi:
Nəhayət, birincidən başqa bütün massivləri ardıcıl olaraq sağdan sola silməlisiniz:
Beləliklə, bu funksiya aşağıdakı Turinq maşını ilə (düzgün) hesablanır.
Turinq maşınının tərifi, işləməsi və təyin edilməsi yolları
Turinq maşını dedikdə, aşağıdakı hissələrdən ibarət olan bəzi hipotetik (mücərrəd) maşın başa düşülür (Şəkil 3.1.)
1) hücrələrə bölünmüş hər iki istiqamətdə sonsuz lent, hər birində əlifbadan yalnız bir simvol, həmçinin boş simvol l ola bilər;
2) istənilən vaxt komplektdən vəziyyətlərdən birində ola bilən idarəetmə cihazı (işçi başlıq). Hər bir ştatda baş hüceyrənin qarşısına qoyulur və ona əlifbadan hərf oxuya (bax) və ya yaza bilər. AMMA.
düyü. 3.1. Turinq maşını
MT-nin işləməsi elementar addımlar (dövrlər) ardıcıllığından ibarətdir. Hər bir addım aşağıdakıları yerinə yetirir:
1. işçi baş personajı oxuyur (baxır);
2. Vəziyyətindən və müşahidə olunan simvoldan asılı olaraq baş simvol yaradır və onu müşahidə olunan hücrəyə yazır (ehtimal ki =) ;
3. baş bir hüceyrəni sağa aparır (R), sol (L) ya da yerində qal (E);
4. Baş fərqli daxili vəziyyətə keçir. (bəlkə =).
Vəziyyət ilkin, son adlanır. Son vəziyyətə daxil olduqda, maşın dayanır.
MT-nin tam vəziyyəti deyilir konfiqurasiya . Bu, lentin hüceyrələrində hərflərin paylanması, işləyən başın və nəzarət edilən hüceyrənin vəziyyətidir. Nəzakətdə konfiqurasiya t kimi yazılır: , burada nəzarət edilən xananın solunda olan alt söz, nəzarət edilən xanadakı hərf, sağdakı alt sözdür.
İlkin konfiqurasiya və yekun standart adlanır.
MT-nin işini təsvir etməyin 3 yolu var:
Komanda sisteminə baxın
Funksiya cədvəli;
Keçidlərin qrafiki (diaqramı).
Onlara misallarla baxaq.
Misal 1Əlifbada iki sözün birləşməsini həyata keçirən MT qurun. Lentdəki sözlər * ilə ayrılır. İlkin konfiqurasiya standartdır.
MT komanda sisteminin forması var:
Dövlətdə baş sağa boş bir xarakterə keçir.
Ən sağdakı simvol silinir.
İlk söz boş olarsa, ulduz işarəsi silinir.
Sağ söz hər bir işarə ilə bir mövqe simvolu ilə sola sürüşdürülür.
Standart hədəf konfiqurasiyasına keçid.
Funksiya cədvəli
| a | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
Cədvəldəki tirelər o deməkdir ki, l-ə ştatlarda rast gəlmək olmaz.
|
|
|||
Standart son konfiqurasiya.
MT-də lüğət funksiyasının hesablanması aşağıdakı kimi başa düşüləcəkdir. İlkin konfiqurasiyada lentə a sözü yazılsın. Əgər dəyər müəyyən edilibsə, onda sonlu sayda addımlardan (dövrlərdən) sonra maşın sözün lentə yazıldığı son konfiqurasiyaya keçməlidir. Əks halda, MT qeyri-müəyyən müddətə işləməlidir.
MT-dən istifadə edərək, rəqəmlər üzərində hesab əməliyyatlarının icrasını təsvir edə bilərsiniz. Bu zaman ədədlər lentdə hansısa say sisteminin rəqəmlərindən ibarət əlifbada sözlər kimi təqdim olunur və bu əlifbaya daxil olmayan xüsusi işarə ilə ayrılır, məsələn, *. Ən çox istifadə olunan sistem bir simvoldan ibarət olan unary sistemdir -1. Lentdə X rəqəmi sözlə, (yaxud qısaldılmış) əlifba ilə yazılır A=(1).
Əgər = olduqda konfiqurasiyanı konfiqurasiyaya uyğunlaşdıran MT varsa, ədədi funksiya Turing mənasında düzgün hesablana bilər (və ya sadəcə hesablana bilər). y, və ya müəyyən edilmədikdə qeyri-müəyyən müddətə işləyir.
Misal 2 Unar kodda iki ədədin toplanması əməliyyatı.
İlkin konfiqurasiya:
Son konfiqurasiya: yəni. Əlavə faktiki olaraq nömrə təyin etməkdən ibarətdir b nömrəyə a. Bunun üçün ilk 1 silinir və * 1 ilə əvəz olunur.
MT-nin təsvirini funksional cədvəl şəklində veririk:
| * | l | ||
| - | |||
| - | |||
| - |
MT-nin təsvirinin yuxarıdakı üsulları praktiki olaraq yalnız sadə alqoritmlər üçün istifadə edilə bilər, çünki mürəkkəb təsvirlər çox çətin olur. Eynilə, rekursiv funksiyaları yalnız ən sadə funksiyalar və superpozisiya, primitiv rekursiya və minimuma endirmə operatorları ilə təsvir etmək olduqca çətin olardı. Buna görə də, primitiv və ya qismən rekursivliyi artıq sübut edilmiş digər funksiyalardan istifadə etməklə funksiyanın primitiv və ya qismən rekursivliyi sübut edilir.
Eynilə, mürəkkəb alqoritmlər üçün Turinq maşınları mövcud MT-lərdən istifadə etməklə qurula bilər. Belə bir tikinti MT tərkibi adlanır.
MT tərkibinin 4 əsas yolunu təsvir edək:
Ardıcıl kompozisiya (superpozisiya);
Paralel kompozisiya;
Budaqlanma
Davamlı kompozisiya maşınlar və lüğət funksiyalarını hesablayan və əlifbada AMMA, maşın adlanır T funksiyasını hesablayan . Ardıcıl kompozisiya aşağıdakı kimi təsvir edilmişdir:
və işarə olunur.
Ardıcıl tərkib adətən alqoritmlərin xətti bölmələrini təsvir etmək üçün istifadə olunur.
Maşının qurulmasının mümkünlüyü haqqında teoremin sübutu T, iki ixtiyari maşının ardıcıl tərkibidir və son vəziyyəti ilkin vəziyyətlə eyniləşdirməklə həyata keçirilir.
Misal 3 a sözünü a*a sözünə çevirən surət maşınından və əlavə maşından istifadə edərək birlik kodda 2*X vurma alqoritmini qurun. İstədiyiniz MT belə görünür:
| | | |
|||||||||||||
| | |
||||||||||||||
Paralel kompozisiya lüğət funksiyalarını hesablayan maşınlar və əlifbalar AMMA Və IN müvafiq olaraq maşının adı T lüğət funksiyasını hesablayan . Burada işarə paralel MT tərkibində sözləri ayırmaq üçün istifadə olunur.
| |
və qeyd olunur: .
Əslində, iki MT-nin paralel tərkibi müxtəlif əlifbalarda 2 sözdən ibarət sözü giriş kimi qəbul edir və 2 sözdən ibarət sözü çıxarır, yəni. eyni vaxtda və müstəqil işləyən iki maşından ibarətdir.
Paralel bir kompozisiya həyata keçirmək üçün iki qatlı lentli bir maşın istifadə olunur. Buna zərurət ondan irəli gəlir ki, və hesablanması zamanla ardıcıl baş verir və hesablanır, məsələn, birinci, a-dan daha çox yer tələb edə bilər və b sözünü korlaya bilər. İki qatlı lent maşını belə işləyir: b sözü ikinci mərtəbəyə yenidən yazılır və birinci mərtəbədə silinir, birinci mərtəbədə hesablanır, ikinci mərtəbədə hesablanır və sonra birinci mərtəbəyə yenidən yazılır, ola bilsin, növbə ilə. .
Paralel kompozisiyanı həyata keçirmək n istifadə olunan maşınlar n– döşəmə lenti.
İki mərtəbəli lentlə MT komandası aşağıdakı kimi yazılır: birinci və ikinci mərtəbələrdə müvafiq olaraq yazılan hərflər haradadır.
Misal 4. Maşınların paralel tərkibini həyata keçirin və , binar sistemdə hesablama funksiyaları və a+b unar sistemdə.
Daxil olan söz aşağıdakı formaya malikdir: .
MT-nin işini əmrlər sistemi ilə təsvir edək:
Sözə doğru sağa hərəkət b
b sözünün ikinci mərtəbəyə yenidən yazılması
A sözünə sola keçin
X-ə 1 əlavə edin.
Sözə doğru sağa hərəkət b.
Nömrələrin eyni vaxtda əlavə edilməsi ilə 1-ci mərtəbəyə qədər siyahıyaalma b a Və b.T müvafiq olaraq. Qıvrımlı mötərizələrdəki əmrlər əmr sisteminə əlavə edildi
Bütün MT-nin son vəziyyəti.
Qeyd etmək lazımdır ki, bütün hallarda, alqoritmin əvvəlində xüsusi dəyərlər üçün ilkin məlumatların yoxlanışını daxil etmək lazımdır (ən çox vaxt 0 üçün), bu tələbə əməl edilməməsi döngəyə səbəb ola bilər. .
MT tərkibi mürəkkəb alqoritmlər qurmaq üçün istifadə edilə bilər. Sual yaranır: hər hansı bir alqoritm MT-nin tərkibi kimi həyata keçirilə bilərmi? Bu sualın cavabı belədir Turinq tezisi , Church tezisinin analoqu: hər hansı bir alqoritm Turing maşınlarından istifadə etməklə həyata keçirilə bilər və əksinə, Turing maşını tərəfindən həyata keçirilən istənilən proses alqoritmdir.
Türinqin tezisi teorem deyil, onu sübut etmək mümkün deyil, çünki qeyri-rəsmi anlayışı ehtiva edir " alqoritm". Bununla belə, uzunmüddətli riyazi təcrübə bu tezisin etibarlı təsdiqidir: 50 il ərzində Turing maşınlarından istifadə etməklə həyata keçirilə bilməyən intuitiv mənada heç bir alqoritm tapılmamışdır.
Turinq maşını (MT) mücərrəd icraçıdır (mücərrəd hesablama maşını).
Alqoritm birləşmələri bir neçə verilmiş alqoritmlərdən yeni alqoritmlər qurmağın bir sıra xüsusi üsullarına verilən addır.
Alqoritmlərin birləşməsinə dair teoremlər alqoritmlərin ümumi nəzəriyyəsinin mühüm hissəsini təşkil edir. Bir dəfə sübut olunduqda, onlar gələcəkdə onları müəyyən edən sxemləri yazmadan mürəkkəb və çətin alqoritmlərin mümkünlüyünə əmin olmağa imkan verir.
Türinq maşını üçün alqoritmlərin birləşmələri Turing maşınlarında əməliyyatlarla təsvir olunur.
1. Kompozisiya əməliyyatı.
M 1 və M 2 eyni xarici əlifba A« (a 0 ,a 1 ,...,a p ) olan Turing maşınları olsun. Onların vəziyyət çoxluqlarını Q1 « (q 0 ,q 1 ,...,q n ) və Q2 « (q 0" ,q 1" ,...,q m" kimi işarə edək.
Tərif.
M 1 və M 2 maşınlarının tərkibi M=M 1 ×M 2 ilə işarələnmiş, proqramı A əlifbasına, Q« (q 0 ,q 1 ,...,qn ,q n) hallar çoxluğuna malik olan maşındır. +1 ,... ,q n+m ) və M 1 və M 2 maşınlarının proqramlarından aşağıdakı kimi alınır: M 1 maşınının proqramında q 1 ( işarəsi olan "üçlüklər" olan hər yerdə. maşının son vəziyyəti M 1), q 0" simvolu ilə əvəz olunur (maşının ilkin vəziyyəti M 2); M 1 və M 2 maşınlarının proqramlarındakı bütün digər simvollar dəyişməz qalır (nəhayət, o M maşınının bütün hallarını yenidən nömrələmək qalır: (q 0 ,q 1" ,q 2 ,...,qn ,q 0 " ,q 2" ,...,qm" )).
Kompozisiya bir maşın kimi "işləməyə" başlayır M 1 , lakin M 1 maşınının dayanmalı olduğu hallarda, q 1-in q 0 " ilə dəyişdirilməsi səbəbindən M 2 maşınının proqramına keçid var. Aydındır ki, kompozisiya əməliyyatı assosiativdir, lakin kommutativ deyil.
Onun işi T1 və T2 maşınlarının ardıcıl işinə bərabərdir.
Şəkildə n=1 və m=1 üçün superpozisiya operatorunu həyata keçirən Turinq maşınlarının tərkibi göstərilir.
Şəkil 1.
Tərif.
Turinq maşınının M iterasiyası maşındır
2. Filialın fəaliyyəti.
M 1 , M 2 və M 3 eyni xarici əlifbası A« (a 0 ,a 1 ,...,ai ,...,aj ,...,ap ) və müvafiq olaraq çoxluqlar olan Turing maşınları olsun. bildirir: Q1 « (q 0 ,q 1 ,...,qn ), Q2 « (q 0" ,q 1" ,...,qm" ), Q3 « (q 0», q 1" ,.. .,ql").
Tərif.
M 1, M 2 və M3 Türinq maşınlarında şaxələnmə əməliyyatının nəticəsi M 1, M 2 və M 3 maşın proqramlarından proqramı aşağıdakı kimi alınan Türinq maşını M olub: maşın proqramı M1 yazılır, sonra maşın M 2 və M 3 proqramları təyin edilir. Əgər a i simvolu M1 maşınının son q 1 vəziyyətində müşahidə edilirsə, onda idarəetmə M 2 maşınına keçir, yəni. q 1 simvolu q 0" işarəsi ilə əvəz olunur və maşın M 2 işə başlayır. Bununla belə, M 1 maşınının q 1 son vəziyyətində aj simvolu müşahidə edilirsə, onda idarəetmə M 3 maşınına keçir. , yəni q 1 simvolu q 0" simvolu ilə əvəz olunur və M 3 maşını işə başlayır. M 1 və M 2 maşınlarının proqramlarındakı bütün digər simvollar dəyişməz olaraq qalır. M maşını son q 1 vəziyyətində başa çatır (nəticədə, M maşınının vəziyyətlərinin davamlı olaraq yenidən nömrələnməsini həyata keçirmək qalır).
M 1, M 2 və M3 Tyurinq maşınlarında budaqlanma əməliyyatının nəticəsi aşağıdakı kimi işarələnir:
İki hərfli Tyurinq maşınları üçün (iki hərfli əlifbalı Tyurinq maşınları) M1, M2 və M3 ixtiyari Tyurinq maşınlarında budaqlanma əməliyyatı aşağıdakı kimi işarələnir:
olanlar. M1 maşınının q 1 vəziyyətində işləməsi zamanı a 0 simvolu müşahidə edilirsə, onda idarəetmə M2 maşınına, əks halda M3 maşınına keçir.
3. Velosiped sürmə əməliyyatı.
M əlifbası A« (a 0 ,a 1 ,...,a p ) və Q« dövlət çoxluğu (q 0 ,q 1 ,...,q n ) olan Türinq maşını olsun.
Tərif.
Döngələmə əməliyyatının nəticəsi Turinq maşını adlanacaq və (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
onun proqramı M maşınının proqramından ardıcıl e əmrini qiaj ®q 1 atr, rн(L,R,L), t=0,1,2,...p simvolu q ilə əvəz etməklə əldə edilir. qs simvolu ilə 1.
2.4 Turinq maşınının variantları
Turing maşın modeli genişləndirməyə imkan verir. İxtiyari sayda lentləri və müxtəlif məhdudiyyətləri olan çoxölçülü lentləri olan Turing maşınlarını nəzərdən keçirmək olar. Bununla belə, bu maşınların hamısı tam Turinqdir və adi Turing maşını ilə modelləşdirilmişdir.
Belə ekvivalentliyə misal olaraq, hər hansı MT-nin yarı sonsuz lentdə işləyən MT-yə endirilməsini nəzərdən keçirin.
Teorem:İstənilən Turing maşını üçün yarı sonsuz lent üzərində işləyən ekvivalent Turing maşını var.
Sübut:
Yu.Q.Karpovun sübutunu nəzərdən keçirək. Bu teoremin sübutu konstruktivdir, yəni biz alqoritm verəcəyik ki, onun vasitəsilə istənilən Türinq maşını üçün elan edilmiş xassə ilə ekvivalent Tyurinq maşını qurula bilər. Əvvəlcə MT iş lentinin hüceyrələrini özbaşına nömrələyirik, yəni lentdə məlumatın yeni yerini müəyyənləşdiririk:
Şəkil 1.
Sonra xanaları yenidən nömrələyirik və MT lüğətində "*" simvolunun olmadığını güman edəcəyik:
Şəkil 1.
2.5 Turinq hesablama qabiliyyəti və həlledicilik
Yuxarıda sübut edilmişdir ki, rekursiv funksiyalardan, Turinq maşınlarından və ya normal Markov alqoritmlərindən istifadə etməklə hesablana bilən funksiyaların sinifləri üst-üstə düşür. Bu bizə “hesablama alqoritmi” anlayışını təsvir metoduna invariant hesab etməyə imkan verir. Fərqlər yalnız alqoritmik obyektlərin istifadəsində müşahidə olunur. Əgər rekursiv funksiyalar üçün obyektlər ədədlər və ədədi funksiyalardırsa və hesablama prosesi superpozisiya, rekursiya, minimuma endirmə və iterasiya operatorları tərəfindən müəyyən edilirsə, Tyurinq maşınları üçün belə obyektlər xarici və daxili yaddaşın əlifbalarının simvollarıdır və hesablamalar. proses çıxış, keçid və baş hərəkətindən istifadə edərək protokolla müəyyən edilir. Normal Markov alqoritmi üçün belə obyektlər sözlər və ya simvol ardıcıllığıdır və hesablama prosesi əvəzetmə qaydaları və ya orijinal simvol ardıcıllığının tərkibini və strukturunu istənilən nəticəyə dəyişən məhsullarla müəyyən edilir.
Arifmetik (ədədi) funksiya diapazonu N çoxluğunun alt çoxluğu, təyinetmə sahəsi isə N çoxluğunun elementi olan funksiyadır.
Alqoritmik problemlər üçün tipik bir vəziyyət, x 1 , x 2 , …, arqumentlərinin tam dəyərlərindən asılı olaraq f(x 1 , x 2 , …, xn) ədədi funksiyasının hesablanması üçün alqoritm tapmaq lazım olduqda olur. xn .
Əgər funksiyanın dəyərini hesablamaq üçün onun arqumentlərinin hər hansı dəyər dəstinə imkan verən (və ya funksiyanın bu çoxluqda müəyyən edilmədiyini göstərən) alqoritm varsa, biz f:N n →N funksiyasını hesablana bilən adlandırırıq. Hesablana bilən funksiyanın tərifində alqoritmin intuitiv konsepsiyasından istifadə edildiyi üçün “hesablana bilən funksiya” termini əvəzinə tez-tez “intuitiv hesablana bilən funksiya” termini istifadə olunur. Beləliklə, bu problemə uyğun arifmetik funksiya intuitiv olaraq hesablana biləndirsə, kütləvi problemin həlli var.
f(x 1 , x 2 , …, xn) funksiyası effektiv hesablana bilən adlanır ki, verilmiş k 1 , k 2 , …, kn arqumentlər üçün f(k 1 ,) funksiyasının qiymətini tapmaq mümkündür. k 2 , …,kn) bəzi mövcud mexaniki prosedurdan (alqoritmdən) istifadə etməklə.
Alqoritm anlayışını aydınlaşdırmaq əvəzinə, “hesablana bilən funksiya” anlayışının dəqiqləşdirilməsini nəzərdən keçirmək olar. Adətən onlar aşağıdakı şəkildə hərəkət edirlər:
1. Tam müəyyən edilmiş funksiyalar sinfi təqdim edilir.
2. Bu sinifin bütün funksiyalarının hesablana bildiyinə əmin olun.
3. Hesablanan funksiyalar sinfinin təqdim edilmiş funksiyalar sinfi ilə üst-üstə düşməsi ilə bağlı fərziyyəni (tezisini) qəbul edin.
Funksiyanı hesablayan alqoritm varsa ona hesablana bilən deyilir. “Hesablanabilirlik” hesablanan funksiyaya və alqoritmə invariant olan alqoritmlər nəzəriyyəsinin əsas anlayışlarından biridir. Hesablana bilən funksiya ilə alqoritm arasındakı fərq, funksiyanın təsviri ilə müstəqil arqumentlərin qiymətləri əsasında onun dəyərlərinin hesablanması üsulu arasındakı fərqdir.
Turinqin tezisi. İstənilən intuitiv alqoritm bəzi Turing maşınından istifadə etməklə həyata keçirilə bilər.
Türinqin tezisindən belə çıxır ki, əgər alqoritmik problemlər yaranarsa, o zaman onları Tyurinq maşınlarının konstruksiyası əsasında həll etmək lazımdır, yəni alqoritmin formallaşdırılmış konsepsiyası kifayətdir. Üstəlik, alqoritmik məsələlərdə söhbət çox vaxt alqoritmin qurulmasından deyil, xüsusi üsulla qurulmuş bəzi funksiyaların hesablanmasından gedir.
Qeyd etmək lazımdır ki, bu hallarda (0,|) əlifbasından istifadə etmək kifayətdir, burada 0 boş simvoldur. Məsələn, 0 daxil olmaqla natural ədədlər bu əlifbada aşağıdakı kimi kodlaşdırılır: 0 - |; 1 - ||; 2-
N - ||…| (n + 1 dəfə). Qismən ədədi n yerli funksiyası f(x1 , x2 , …, xn) onu aşağıdakı mənada hesablayan M maşını varsa, Turinq hesablana bilən adlanır: 1. Arqument qiymətləri çoxluğu varsa
ÖZÜNÜ TƏTBİQ PROBLEMİ
Turing maşınının tərifinə görə, bu üçlüdür T=
P: qi a aj a ® q r a a s a S t a , a = 1, 2, …, k , harada S1-R, S2- L, S3- C . (*)
Bu halda bəzi ümumi əlifbaların olduğunu güman etmək olar A0 Və Q0, hansı simvollarda yazılır a Və q bütün Turing maşınları üçün. Sonra simvollar qi a, aj a , q r a, a s a, S t aəlifbaların simvollarıdır A0 Və Q0.
Bu yanaşma bütün Turing maşınlarını nömrələməyə, yəni hər bir maşına bu maşına xas olan müəyyən nömrəni (kod) təyin etməyə imkan verir ki, onun vasitəsilə onu digər maşınlardan fərqləndirmək mümkün olsun. Burada nömrələmə üsullarından birini nəzərdən keçiririk.
Turing maşınlarının Gödel nömrələnməsi. Qoy olsun p1, p2, p3 , … - artan qaydada düzülmüş sadə ədədlər ardıcıllığı, məsələn, 2, 3, 5, 7, 11, 13, …
Proqramla (*) Turinq maşını nömrəsi nömrə çağırdı
n(T) = .
Misal
Bir funksiyanı həyata keçirən maşın S(x)= x + 1 , əlifbada proqramı var {0, } . Bu proqramın sayı nəzərə alınmaqla a 0 = 0 , a 1= | sayı olacaq:
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Aydındır ki, bütün natural ədədlər Turing maşınının nömrələri deyil. Digər tərəfdən, əgər n bəzi maşınların sayıdır, ümumi əlifbalarda, onda onun proqramı bu nömrədən unikal şəkildə bərpa edilə bilər.
Maşın T sözünə tətbiq edilir n(T)(yəni öz nömrənizin koduna), öz-özünə tətbiq olunur .
Həm öz-özünə tətbiq olunan maşınları, həm də öz-özünə tətbiq olunmayan maşınları qurmaq mümkündür. Məsələn, verilmiş nümunədəki maşın öz-özünə tətbiq olunur. Maşın T proqramın sağ hissələrində (cədvəlin mətnində) fasilə xarakteri daşımayan , heç bir sözə və dolayısı ilə sözə şamil edilmir. n(T).
Özünü tətbiq etmək problemi aşağıdakılardan ibarətdir: hər hansı bir Turinq maşını verildikdə onun öz-özünə tətbiq edilib-edilmədiyini müəyyən edəcək bir alqoritmi göstərmək.
Türinqin tezisinə görə, belə bir alqoritmi Türinq maşını şəklində axtarmaq lazımdır. Bu maşın bütün Turing maşınlarının nömrə kodlarına şamil edilməli və sınaqdan keçirilmiş maşınların kodlarının işlənməsi nəticəsindən asılı olaraq müxtəlif son konfiqurasiyalara malik olmalıdır.
Məsələn, bu maşın T koda tətbiq olunur n(T * ) . Əgər maşın T * öz-özünə tətbiq oluna bilər, sonra maşının son konfiqurasiyası T formasına malikdir a" q0 | B", və əgər maşın T * öz-özünə tətbiq olunmur, onda maşının son konfiqurasiyası T formasına malikdir a" q0 0B ". Budur a, B, a, B- sözlər.
teoremÖz-özünə tətbiq oluna bilmə problemi alqoritmik olaraq həll edilmir, yəni yuxarıdakı mənada bu problemi həll edən Tyurinq maşını yoxdur.
Teoremdən belə çıxır ki, öz-özünə tətbiq oluna bilmə məsələsinin həlli üçün ümumi alqoritm yoxdur. Xüsusi hallarda belə alqoritmlər mövcud ola bilər.
Gəlin bu teoremin nəticələrindən ilkin sözə tətbiq oluna bilmə məsələsinin qərarsızlığını sübut etmək üçün istifadə edək.
Başlanğıc sözə tətbiq olunma problemi aşağıdakılardan ibarətdir: maşın vasitəsilə alqoritm yaradın T və söz X uyğun maşın quraşdıracaq T yeri gəlmişkən X ya yox (əks halda dayandırma problemi).
Turing maşınları baxımından, öz-özünə tətbiq oluna bilmə probleminin formalaşdırılmasına bənzər şəkildə, bu problem aşağıdakı kimi tərtib edilmişdir: formanın bütün sözləri üçün tətbiq oluna biləcək bir maşın qurmaq mümkündürmü? n(T) 0 X , harada T təsadüfi maşın, X ixtiyari bir sözdür və əgər maşın T sözünə şamil edilir X a" q0 |B" , və əgər avtomobil T sözünə aid edilmir X , son konfiqurasiyaya gətirib çıxaracaq a" q0 0B" . Budur a" , B" Və a", B"- ixtiyari sözlər.
teorem Başlanğıc sözə tətbiq olunma problemi alqoritmik cəhətdən həll olunmur, yəni yuxarıdakı mənada bu problemi həll edən Tyurinq maşını yoxdur.
Özünü tətbiq etmək problemi üçün yuxarıda qeyd edildiyi kimi, ilk ilkin addım nömrələmədir. Buna görə də, aşağıda bu məsələ ardıcıl olaraq alqoritmlər və onun üç əsas alqoritmik modeli üçün nəzərdən keçirilir və həll edilir.
Alqoritm nömrələmə
Alqoritmlərin nömrələnməsi onların öyrənilməsində və təhlilində mühüm rol oynayır. Hər hansı bir alqoritm sonlu söz kimi təyin oluna bildiyindən (bəzi əlifbanın simvollarının sonlu ardıcıllığı kimi təmsil olunur) və sonlu əlifbanın bütün sonlu sözlərin çoxluğu hesablana bilən olduğundan, bütün alqoritmlərin çoxluğu da hesablana bilir. Bu, natural ədədlər çoxluğu ilə alqoritmlər çoxluğu arasında tək-tək xəritələşmənin mövcudluğu, yəni hər bir alqoritmə ədədin təyin edilməsi imkanı deməkdir.
Alqoritmlərin nömrələnməsi eyni zamanda bütün alqoritmik hesablanmış funksiyaların nömrələnməsidir və istənilən funksiyanın sonsuz sayda ədədi ola bilər.
Nömrələmənin mövcudluğu alqoritmlərlə rəqəmlərlə eyni şəkildə işləməyi mümkün edir. Nömrələmə xüsusilə digər alqoritmlərlə işləyən alqoritmlərin öyrənilməsində faydalıdır.
İlkin obyektlər X çoxluğu və arzu olunan Y obyektləri çoxluğu ilə hansısa kütləvi məsələ olsun. Kütləvi məsələnin həllinin mövcudluğu üçün X və Y çoxluqlarının elementlərinin konstruktiv obyektlər olması zəruridir. Buna görə də bu çoxluqların elementlərini natural ədədlərlə sadalamaq olar. Qoy x∈ X hansısa ilkin obyekt olsun, onun nömrəsini n(x) ilə işarə edək. Kütləvi məsələdə ilkin x obyektindən n(y) ədədi ilə istənilən y∈ Y obyektini almaq tələb olunursa, o zaman f arifmetik funksiyasını təyin edirik: Nn →N belə ki, f(n(x))= n(y).
Kütləvi məsələlər üçün arifmetik funksiyaların qurulmasına nümunə olaraq, kütləvi məsələləri nəzərdən keçirin.
1. Əgər natural ədədlərdən ibarət ] massivi verilmişdirsə, o zaman onunla əlaqələndirilə bilər natural ədəd 2x1, 3x2,... p(n)xn , burada p(n) olur n-ci əsas nömrə. Məsələn, uzunluğu 5 olan bir massivi nəzərdən keçirək:
] 2x13x25x37x411x5.
Bu nömrələmə f arifmetik funksiyasını təyin edir (məsələn, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. İstənilən rasional ədədin hansısa natural ədədi var. Problemin arzu olunan obyektləri dəstinin sadalanması mənasızdır:
("bəli", "yox") a (1, 0). Verilmiş kütləvi problem üçün siz əvvəlki misaldakı hiylədən istifadə edərək bir arqumentin arifmetik funksiyasını qura bilərsiniz və ya üç arqumentin funksiyasını (orijinal üçlüyün üç ədəd elementi) nəzərdən keçirə bilərsiniz.
3. Proqram mətnlərinin nömrələnməsi aşağıdakı kimi həyata keçirilə bilər: istənilən proqramı 256-arlıq say sistemində ədədin qeydi kimi qəbul etmək olar (əgər proqramın yazılması üçün ASCII cədvəl simvollarından istifadə edilmişdisə).
Kütləvi problemdən arifmetik funksiyaya keçid bizə kütləvi problemin həllinin mövcudluğu məsələsini onun arqumentindən arifmetik funksiyanın qiymətlərini hesablamaq üçün effektiv bir yolun mövcudluğu məsələsinə endirməyə imkan verir( s).
Rəqəmlər dəstlərinin nömrələnməsi
Alqoritmlər nəzəriyyəsində bir neçə dəyişənin funksiyalarının öyrənilməsini bir dəyişənin funksiyalarının öyrənilməsinə qədər azaltmağa imkan verən bir texnika geniş yayılmışdır. O, ədədlər çoxluqlarının sadalanmasına əsaslanır ki, ədədlər çoxluğu ilə onların ədədləri arasında biyektiv uyğunluq olsun və onun sayını ədədlər çoxluğundan və ədədlər çoxluğunun sayından müəyyən edən funksiyalar ümumi rekursiv olsun. . Məsələn, iki müstəqil dəyişəni (x, y) ehtiva edən funksiya üçün bu xəritələşdirmə h(x, y) belə görünə bilər:
Şəkil 1.
Qoy (x, y) cütləri qismən sıralanmış N çoxluğu təşkil etsin (2) . Verilmiş h(x, y) = n, onda tərs xəritələşmə var: x = h -1 1 (n) və y= h -1 2 (n), yəni h(h -1 1 (n), h - 1 2 (n)) = n. Bu, hər hansı bir cüt (x, y) üçün n sayını hesablamağa və əksinə, n rəqəmindən x və y dəyərlərini hesablamağa imkan verir:
Bu qaydalardan istifadə edərək, h 2 (x, y, z) = h (h (x, y), z) = n üçlüyünün nömrələnməsini və əksinə, üçlüyün sayına görə - x dəyərlərini hesablamaq olar. , y, z. Məsələn, h 2 (x, y, z) = n olarsa, z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ), h -1 2 (n)). Üçlüklər (x, y, z) qismən sıralanmış N çoxluğunu təşkil edir (3) . Eynilə, ixtiyari sayda ədədlər üçün bizdə:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Əgər h n-1 (x1, x2,…, xn)=m, onda xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ................................, x2 = h -1 2 (h -1 1 (... h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
N (1) , N (2) ,..., N (i) ,..., N(n) dəstlərinin nömrələnməsinə malik olmaqla, burada N (i) (i) ədədlər çoxluğudur, M = N (1) N (2) ... N (i) .. N(n) , burada M N. İstənilən n N üçün bizdə h(x1,x2, ..., xn )= h(hn −1 (x1,x2,..., xn), n −1).
Əgər h(x ,1x ,2..., x)n = m, onda hn−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Yuxarıdakı düsturlardan istifadə edərək, x1, x2,…, xn dəyərlərini bərpa edə bilərsiniz.
Oxşar məlumat.
Turing maşınının işləməsi:
Alqoritmin üç əsas anlayışından ikinci tərif maşın riyaziyyatı ilə bağlıdır. Alqoritm istənilən vaxt ən sadə əməliyyatları yerinə yetirməyə qadir olan ən sadə deterministik cihaz hesab olunur. Əsas model Turing maşınıdır.
Turing maşını üç əlifba ilə işləyir:
1. giriş əlifbası AMMA={a 0…a n), onun köməyi ilə giriş, aralıq, çıxış məlumatları qeydə alınır. a 0– boş simvol (əhəmiyyətli olmayan sıfır, Ù, IN, #), a 1– 1 və ya |
2. daxili əlifba, yaxud dövlətlərin əlifbası Q={q0…qm}, q0- son vəziyyət q 1- ilkin vəziyyət q 0 …q n- iş şəraiti
3. əlifbanı dəyişdirin (L, V, N) və ya (-1, +1, 0) (sola, sağa, yerində)
Turing maşını aşağıdakı hissələrdən ibarətdir:
1) lent, hər iki istiqamətdə potensial sonsuzdur. Potensial sonsuzluq o deməkdir ki, zamanın hər anında lentə sonlu söz yazılır, lakin lazım gələrsə, sözün solunda və sağında lazımi sayda xanalar tamamlana bilər. Lent hər birində giriş əlifbasının yalnız bir simvolunu ehtiva edən hüceyrələrə bölünür. Boş xanalara boş simvol yazılır. Hüceyrədəki məlumatı silmək lazımdırsa, ona boş simvol yazmaq kifayətdir.
2) nəzarət cihazı(UU), proqramın köməyi ilə Turing maşınına nəzarət edir. CU istənilən vaxt yalnız əlifbanın dövlətlərindən birində ola bilər Q.
3) baş(oxucu və yazıçı) hər an aşağıdakı hərəkətləri yerinə yetirir
xanada yazılmış simvolu oxuyur
onu əlifbanın başqa simvolu ilə əvəz edir AMMA və ya eyni şəkildə buraxın
lent boyunca bir hüceyrə ilə sağa, sola sürüşür və ya yerində qalır
Turing maşınının qaydası:
Turinq maşını, vəziyyətdə olmaq qi və personajı oxumaq aj, bu xanaya simvol yazır a k, dövlətə gedir q e, növbəni yerinə yetirir. Eyni zamanda, maşının bir əmri yerinə yetirdiyini söyləyirlər: a j q i® a k q e S SО(L, P, N)
Əmrlər toplusu MT proqramı adlanır.
a j q i– əmrlərin ilkin simvolları fərqli olmalıdır. Bu şərt yerinə yetirilərsə, maşın çağırılır deterministik , əks halda - qeyri-deterministik . Maşın diskret vaxtlarda işləyir.
Bu cür, Tam təsvir Turing maşınının hər anında, onun sonrakı davranışını təyin etmək üçün aşağıdakılar haqqında məlumat var:
maşının yerləşdiyi daxili vəziyyət, lentdə yazılan söz və oxunan simvol haqqında Bu an vaxt. Turing maşınının tam vəziyyəti çağırılacaq konfiqurasiya.
Turing maşınının işi konfiqurasiyalar ardıcıllığı kimi təqdim edilə bilər k 1® k2®…® k n.
Defolt ilkin konfiqurasiya ən soldakı boş olmayan simvolu vəziyyətə oxumaqdır q 1
Standart son konfiqurasiya - maşın son vəziyyətə girdi:
Maşın son vəziyyətə daxil olubsa, bu, verilmiş giriş sözünə şamil edilir, qeyri-müəyyən müddətə işləyirsə, maşın verilmiş sözə aid deyil.
MT giriş əlifbası, dövlətlərin əlifbası və proqramdan ibarət dəstdir. M=
Maşın proqramı aşağıdakı kimi təyin edilə bilər:
1) əmrlərin siyahısı: a j q i® a k q n S
2) cədvəldən istifadə etməklə
| a 0 | a 1 | a 2 | |
| q0 | a k, q m, S | ||
| q 1 |
3) predikat qrafikindən istifadə etməklə (təpə nöqtələri vəziyyətlərdir, hər bir əmr qövsə uyğundur)
Turinq maşınlarının dizaynı:
Turing maşınını dizayn edin - onun proqramını qurun. O, iki mərhələdə baş verir:
1) həll olunan məsələnin alqoritminin şifahi təsviri
2) alqoritmin şifahi təsvirinin Turinq maşınının dilinə tərcüməsi (bunun üçün, A, Q, P)
Misal: f(n)=n+1 funksiyasını qiymətləndirən Turinq maşını qurun, burada n binar sistemdə verilir.
AMMA={0,1,a 0), Q çoxluğu proqramın qurulması prosesində təyin olunur.
Alqoritm:
1. başını həddindən artıq sağ vəziyyətdən həddindən artıq sola köçürün
2. əgər maşın həddindən artıq sağ vəziyyətdə 0 oxuyursa, onu 1-ci xanaya qoyun və dayanın, baş 1-i oxuyursa, onu 0-cı xanaya qoyun və bir addım sola keçin.
2-ci addımı təkrarlayın
Misal: Lentdə natural onluq ədəd yazılır. Bu rəqəmi 1 artıran Turinq maşını qurmaq lazımdır. İlkin olaraq baş rəqəmin birinci rəqəmini göstərir. Alırıq: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0 ), Q = (q 1 , q 2 , q 0 ). P - cədvələ baxın.
| q 1 | 0>q1 | 1>q1 | 2>q1 | 3>q1 | 4>q1 |
| q2 | 1=q0 | 2=q0 | 3=q0 | 4=q0 | 5=q0 |
| a 0 | |||||
| 5>q1 | 6>q1 | 7>q1 | 8>q1 | 9>q1 | a 0 |
| 6=q0 | 7=q0 | 8=q0 | 9=q0 | 0
|
Ümumi fikir - başı nömrənin son rəqəminə keçirin və bu rəqəm 9 deyilsə, onu bir artırın, əks halda onu sıfıra çevirin və əvvəlki xanaya keçin.
Maşınların tərkibi:
Maşın tərkibi iki maşının ardıcıl icrasıdır.
T 1=(A 1, Q1, P 1) T 2=(A2, Q2, P 2) Q1Ç Q2=Æ
Tərkibi maşınlar T 1° T 2 maşını çağırdı T(A, Q, P), harada AMMA=A 1È A2; Q=(Q1È Q2)\{q 10} (q 10- son vəziyyət T 1). Maşın T aşağıdakı qaydaya uyğun işləyir: U- bir söz T(U)=T 1° T 2(U)=T 2(T 1(U))
teorem. Maşınların tərkibi T 1° T 2 mövcuddur.
Q1={q 10, q 1,…, q n}
Q2={q 20, q` 1 , …, q`n), sonra Q qurmaq üçün q 10 vəziyyətini çıxarırıq, adını dəyişdiririk q n +1 , ikinci maşının ilkin vəziyyəti ilə üst-üstə düşür və bütün digər vəziyyətlər içərisindədir q` i = q n + 1 .
Turing hesablana bilən funksiyalar:
f(x 1 …x n) funksiyası çağırılır Turing hesablanabilir arqument dəyərləri verildikdə bu funksiyanın dəyərini qiymətləndirən bir Turing maşını varsa. f(x 1 …x n) funksiyası natural ədədlər çoxluğunda müəyyən edilir, lakin alqoritmlər nəzəriyyəsi NÈ(0) natural ədədlərin genişləndirilmiş çoxluğunu nəzərdən keçirir.
Lentdə f(x 1 ... x n) funksiyasının arqumentləri aşağıdakı söz kimi təqdim olunur:
Hər bir arqument bu arqumentin dəyəri qədər çubuqlara uyğun gəlir. Əgər f funksiyası x 1 ... xn dəyişəninin verilmiş qiymətlər dəstində müəyyən edilirsə, o zaman Turing maşınının işləməsi nəticəsində lentdə cərgədə yazılan çubuqların sayı bərabər olmalıdır. bu çoxluqdakı funksiyanın dəyərinə. Əgər f funksiyası verilmiş çoxluqda müəyyən edilməmişdirsə, o zaman Turinq maşını qeyri-müəyyən müddətə işləməlidir.
İlkin konfiqurasiya - ən soldakı çubuğu oxumaq.
Məqsəd: Tyurinq maşınlarının tərkibindən istifadə etməklə alqoritmlərin yazılması üzrə praktiki bacarıqlar əldə etmək.
Nəzəri məlumat
MT-nin təsvirinin yuxarıdakı üsulları praktiki olaraq yalnız sadə alqoritmlər üçün istifadə edilə bilər, əks halda təsvir çox çətin olur. Mürəkkəb alqoritmlər üçün Turinq maşınları artıq mövcud olan elementar MT-lərdən istifadə etməklə tikilə bilər və belə bir konstruksiya adlanır. tərkibi MT.
MT tərkibinin 4 əsas yolunu təsvir edək:
Ardıcıl kompozisiya (superpozisiya);
Paralel kompozisiya;
Budaqlanma
1. Tyurinq maşınlarının ardıcıl tərkibi
Davamlı kompozisiya və ya superpozisiya Turinq maşınları və 
Və 
əlifbada AMMA, maşını çağırdı M funksiyasını hesablayan 
.
Ardıcıl kompozisiya aşağıdakı kimi təsvir edilmişdir:
və işarələnmişdir 
və ya 
.
2. Tyurinq maşınlarının paralel tərkibi
Paralel kompozisiya
maşınlar 
Və 
, hesablama lüğəti funksiyaları 
Və 
əlifbalarda AMMA Və IN, müvafiq olaraq maşının adı M lüğət funksiyasını hesablayan . Budur işarə 
paralel MT tərkibində sözləri ayırmaq üçün istifadə olunur.
Paralel kompozisiya MT 
Və 
aşağıdakı kimi təsvir edilmişdir:
və işarə olunur: 
.
Əslində, iki MT-nin paralel tərkibi müxtəlif əlifbalarda 2 sözdən ibarət sözü giriş kimi qəbul edir və eyni zamanda 2 sözdən ibarət sözü də çıxarır, yəni. eyni vaxtda və müstəqil işləyən iki maşından ibarətdir. Paralel bir kompozisiya həyata keçirmək üçün iki qatlı lentli bir maşın istifadə olunur.
İki qatlı lent maşını aşağıdakı kimi işləyir:
1) söz 
lentin ikinci mərtəbəsində yenidən yazılmış və birincisində silinmiş,
2) hesablanmışdır 
birinci mərtəbədə,
3) hesablanır 
İkinci mərtəbədə
4)
birinci mərtəbəyə, ehtimal ki, bir növbə ilə yenidən yazılmışdır.
İki qatlı lentlə MT əmri aşağıdakı kimi yazılır:
,
harada 
- birinci və ikinci mərtəbələrdə müvafiq olaraq yazılmış məktublar. Sözlərin uzunluqlarını qeyd edin 
, müvafiq olaraq, 
.
İki qatlı lentlə Turinq maşınının işini nümayiş etdirəcəyik. Ümumiyyətlə, söz uzunluğu 
Və 
bir-biri ilə üst-üstə düşmür, lakin təsvirin sadəliyi üçün onların bərabər olduğunu düşünürük. Sonra iki mərtəbəli lentlə MT-də 1)-4) bəndlərinin yerinə yetirilməsi aşağıdakı kimi aparılır:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paralel kompozisiyanı həyata keçirmək n Turinq maşınlarından istifadə olunur n– döşəmə lenti.
3. Türinq maşınlarının tərkibində budaqlanma və ya şərti budaqlanma
Turing maşınları verilmişdir 
Və 
, hesablama lüğəti funksiyaları 
Və 
, və maşın 
, bəzi predikatı qiymətləndirir P(
)
bərpa ilə (yəni sözü silmədən
),
sonra budaqlanmağı həyata keçirmək üçün Turinq maşını tikilə bilər 
, funksiyanı hesablayan:
Turing maşınlarının kompozisiya diaqramlarında budaqlanması aşağıdakı kimi təsvir edilmişdir:
və işarələnmişdir 
, burada 
- maşının nəticəsi 
, əgər predikat "1" dəyərlərini alır P(
)=
”doğru”
və əgər predikat varsa "0" P(
)=
“yalan”
,
giriş sözünün surətinin çıxarılmasını həyata keçirən Turing maşınıdır 
.
4 . Turing maşınlarının tərkibində dövr
Velosiped tərkibində MT budaqlanma ilə eyni prinsiplərə əsasən həyata keçirilir.
" qədər P(
)=
”doğru”
, yerinə yetirmək 
»,
harada
- ilk edamdan əvvəl lentdəki söz 
və növbəti edamdan sonra .
Dövrün təsviri üçün bəzi qeydləri təqdim edirik, qoy:
predikatın hesablanmasını həyata keçirən Turinq maşınıdır P(
)
;
–Giriş sözünün surətinin çıxarılmasını həyata keçirən MT 
;
-MT, bir dövrədə icra edilir və həyata keçirilir 
;
–MT, döngədən çıxdıqda və həyata keçirərkən yerinə yetirilir 
.
Sonra, Turing maşınlarının tsiklik tərkibi və ya dövrü aşağıdakı kimi təsvir edilə bilər:
Turing maşınlarının kompozisiyaları ilə proqramlaşdırma:
1) onların blokları elementar MT-lərə uyğun gələn detallılıq dərəcəsinə malik mürəkkəb alqoritmlərin blok-sxemlərinin qurulması;
2) sadə blokları həyata keçirən elementar MT-lərin qurulması;
3) elementar MT-lərin MT-lərin tərkibinə birləşdirilməsi.
Misal. Tətbiq edən MT kompozisiyasını qurun 
.
– Giriş sözünün surətinin çıxarılmasını həyata keçirən Turinq maşını;
–MT, sabitin sıfıra təyin edilməsi funksiyasını həyata keçirir;
– Bərpa ilə MT hesablama predikatı 
;
– Seçim funksiyasını həyata keçirən MT 
- o arqumentdən 
arqumentlər
– arqumenti azaltma funksiyasını həyata keçirən MT 
birlik kodda 1 (ən soldakı simvolu silir);
– Uniar kodda iki ədədin əlavə edilməsini həyata keçirən MT.
Qeyd etmək lazımdır ki, istənilən halda, alqoritmin icrasının əvvəlində daxil edilmiş məlumatların düzgünlüyünü yoxlamaq lazımdır (məsələn, bölgü zamanı arqumentin 0-a bərabərliyi).