ტურინგის მანქანა: განსხვავება გადახედვებს შორის

არ არის რედაქტირების რეზიუმე
(ახალი გვერდი: '''ტურინგის მანქანა''' არის ჰიპოთეზური მექანიზმი, რომელიც მან...)
 
[[Image:Maquina.png|thumb|ტურინგის მანქანის მხატვრული წარმოდგენა]]
 
'''ტურინგის მანქანა''' არის ჰიპოთეზური მექანიზმი, რომელიც მანიპულირებას უკეთებს სიმბოლოოებს ფირზე, შესაბამისი ცხრილის წესების გამოყენებით. მიუხედავად მისი სიმარტივისა, ტურინგის მანქანას შეუძლია ნებისმიერი [[კომპიუტერული]] [[ალგორითმის]] ლოგიკის სიმულაცია და ის განსაკუთრებით გამოიყენება [[პროცესორის]] ფუნქციების გასამარტად.
 
 
უფრო დაწვრილებით, ტურინგის მანქანა შედგება:
<ol>
1. <li>'''ფირით''', რომელიც დაყოფილია უჯრებად ერთი-მეორის მიყოლებით. ყოველი უჯრა შეიცავს სიმბოლოს სასრული ანბანიდან. ანბანი შეიცავს პეციალურ ''ცარიელ'' სიმბოლოს (ამ შემთხვევაში წერია როგორც ‘0’) და ერთი-ორ სხვა სიმბოლოს. უჯრები რომელშიც არაფერია არ წერია, ვუშვებთ რომ შეიცვას ცარიელ სიმბოლოს.</li>
2. <li>'''თავი''', რომელიც კითხულობს ან წერს სიმბოლოებს და შემდეგ ფირი გადაადგილდება მარჯვნივ ან მარცხნივ (მხოლოდ ერთი უჯრით). ზოგი მოდელის შემთხვევაში თავი გადაადგილდება და ფირი უძრავია.</li>
3. <li>'''მდგომარეობის შემნახველი''', რომელიც ინახავს ტურინგის მანქანის მდგომარეობას. ფირზე არის ერთი სპეციალური ''საწყისი მდგომარეობა'', სადაც ტურინგიც მანქნა ინიციალიზირდება.</li>
4. <li>სასრული '''ცხრილი''' (ხშირად მოიხსენიება, როგორც '''მოქმედების ცხრილი''' ან '''გარდამავალი ფუნქცია'''). მაგალითად, მოცემულია ''მდგომარეობა''(qiq<sub>i</sub>), სადაც მანქანა არის ''და'' კითხულობს ''სიმბოლოს''(aja<sub>j</sub>) , რომელიც ეუბნება შემდეგს:
• წაშალოს ან ჩაწეროს სიმბოლო (შეცვალოს აჯ აჯ1-ით), შემდეგ
<ul>
• შეიცვალოს მდგომარეობა (გადაადგილდეს მარჯვნიც ან მარცხნივ)
<li>წაშალოს ან ჩაწეროს სიმბოლო (შეცვალოს აჯ აჯ1-ით), შემდეგ</li>
<li>შეიცვალოს მდგომარეობა (გადაადგილდეს მარჯვნიც ან მარცხნივ) </li>
</ul>
</li>
</ol>
 
მნიშვნელოვანია ის ფაქტი, რომ ტურინგის მანქანის ყველა ნაწილი და მოქმედება არის ''სასრული'', ''დისკრეტული'' და ''გარჩევადი''. ის არის პოტენციურად ულიმიტო ფირის რაოდენობა, რომელიც იძლევა უსაზღვრო [[კომპიუტერის მეხსიერება|მეხსიერებას]].
 
==ფორმალური განსაზღვრება==
 
ტურინგის მანქანა ფორმალურად არის განსაზღვრული 7-ნაწილისგან, <math>M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> სადაც:
 
* <math>Q</math> სასრული, არაცარიელი ''მდგომარეობების'' სიმრავლე
* <math>\Gamma</math> სასრული, არაცარიელი ''ფირის ანბანის/სიმბოლოების'' სიმრავლე
* <math>b \in \Gamma</math> ''ცარიელი სიმბოლო''
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> ''შემომავალი სიმბოლოების'' სიმრავლე
* <math>q_0 \in Q</math> ''საწყისი მდგომარეობა''
* <math>F \subseteq Q</math> ''საბოლოო'' მდგომარეობების სიმრავლე
* <math>\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math> ''გარდამავალი ფუნქცია'', სადაც L არის მარცხენა გადაადგილება, R-კი მარჯვენა.
4

რედაქტირება