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

GioGziro95-ის რედაქტირებები გაუქმდა; აღდგა MIKHEIL-ის მიერ რედაქტირებული ვერსია
(GioGziro95-ის რედაქტირებები გაუქმდა; აღდგა MIKHEIL-ის მიერ რედაქტირებული ვერსია)
{{წყარო}}
[[Image:Maquina.png|thumb|ტიურინგისტურინგის მანქანის მხატვრული წარმოდგენა]]
 
'''ტიურინგისტურინგის მანქანა''' — ჰიპოთეტური მექანიზმი, რომელიც მანიპულირებას უკეთებს სიმბოლოოებს ფირზე, შესაბამისი ცხრილის წესების გამოყენებით. მიუხედავად მისი სიმარტივისა, ტიურინგისტურინგის მანქანას შეუძლია ნებისმიერი [[კომპიუტერული]] [[ალგორითმის]] ლოგიკის სიმულაცია და ის განსაკუთრებით გამოიყენება [[პროცესორის]] ფუნქციების გასამარტად.
 
„ტიურინგის“„ტურინგის“ მანქანა გამოიგონა [[ალან ტიურინგმატურინგმა]] 1936 წელს და მას ა-მანქანა უწოდა(ავტომატური მანქანა). ტიურინგისტურინგის მანქანა არ შექმნილა პრაქტიკული კომპიუტერული გამოყენებისთვის. მისი შექმნის მიზანი იყო, ყოფილიყო ჰიპოთეტური მექანიზმი, რომელიც კომპიუტერის ანალოგს წარმოადგენდა. ტიურინგისტურინგის მანქანა ეხმარება მეცნიერებს, გაიგონ მექანიკური შესაძლებლობების საზღვრები.
 
ტიურინგმატურინგმა, 1948 წელს, მის მანქანას მოკლე განმარტება მისცა: „გონივრული მანქანა“ ( "Intelligent Machinery").
 
ტიურინგისტურინგის მანქანას, რომელსაც შეუძლია ნებისმიერი სხვა ტიურინგისტურინგის მანქანის სიმულაცია, [[უნივერსალური ტიურინგისტურინგის მანქანა]] ('''UTM''', or simply a '''universal machine''') ეწოდება. უფრო მათემატიკურად-ორიენტირებული განსაზღვრება მას მისცა [[ალონსო ჩარჩმა]], რომლის სამუშაო [[ლამბდა-კალკულუსის]] შესახებ დაერთო ტიურინგისტურინგის ოფიციალურ თეორემას და მას [[ჩარჩ-ტიურინგისტურინგის თეზისი]] ეწოდა. თეზისი ხაზს უსვამს, რომ ტიურინგისტურინგის მანქანა ნამდვილად ემსახურება ცნებას, ეფექტიანი მეთოდებისა, [[ლოგიკასა]] და [[მათემატიკაში]] და ეხმარება [[ალგორითმის]] ზუსტ განმარტებას.
==არაფორმალური განსაზღვრება==
:''ტიურინგისტურინგის მანქანის გალერეა, ნახეთ აქ [[Turing machine gallery]].''
 
ტიურინგისტურინგის მანქნა არის მათემატიკური მოდელი, რომელიც მექანიკურად აკეთებს ოპერაციებს ფირზე. ამ ფირზე არის სიმბოლოები, რომელსაც მანქანა ან წერს ან კითხულობს, ოღონდ სათითაოდ, ფირის თავის გამოყენებით. ოპერაცია განსაზღვრულია ელემენტარული ინსტრუქციების სასრული სიმრავლით. მაგ: „42-მდგომარებაში თუ შეგხვდება 0, შეცვალე 1-ით; თუ სიმბოლო არის 1, გადადი მე-17 მდგომარებოაში და ა.შ. ორიგინალ სტატიაში ("On computable numbers, with an application to the [[Entscheidungsproblem]]") ტიურინგიტურინგი იგონებს არა მექანიზმს, არამედ ადამიანს, რომელსაც [[კომპიუტერს]] არქმევს და რომელიც ასრულებს ამ დეტერმინისტულ ქმედებებს მონურად.
 
[[Image:Turing machine 2b.svg|thumb|right|300px|]]
 
უფრო დაწვრილებით, ტიურინგისტურინგის მანქანა შედგება:
<ol>
<li>'''ფირით''', რომელიც დაყოფილია უჯრებად ერთი-მეორის მიყოლებით. ყოველი უჯრა შეიცავს სიმბოლოს სასრული ანბანიდან. ანბანი შეიცავს პეციალურ ''ცარიელ'' სიმბოლოს (ამ შემთხვევაში წერია როგორც ‘0’) და ერთი-ორ სხვა სიმბოლოს. უჯრები რომელშიც არაფერია არ წერია, ვუშვებთ რომ შეიცვას ცარიელ სიმბოლოს.</li>
<li>'''თავი''', რომელიც კითხულობს ან წერს სიმბოლოებს და შემდეგ ფირი გადაადგილდება მარჯვნივ ან მარცხნივ (მხოლოდ ერთი უჯრით). ზოგი მოდელის შემთხვევაში თავი გადაადგილდება და ფირი უძრავია.</li>
<li>'''მდგომარეობის შემნახველი''', რომელიც ინახავს ტიურინგისტურინგის მანქანის მდგომარეობას. ფირზე არის ერთი სპეციალური ''საწყისი მდგომარეობა'', სადაც ტიურინგისტურინგის მანქანა ინიციალიზირდება.</li>
<li>სასრული '''ცხრილი''' (ხშირად მოიხსენიება, როგორც '''მოქმედების ცხრილი''' ან '''გარდამავალი ფუნქცია'''). მაგალითად, მოცემულია ''მდგომარეობა''(q<sub>i</sub>), სადაც მანქანა არის ''და'' კითხულობს ''სიმბოლოს''(a<sub>j</sub>) , რომელიც ეუბნება შემდეგს:
<ul>
</ol>
 
მნიშვნელოვანია ის ფაქტი, რომ ტიურინგისტურინგის მანქანის ყველა ნაწილი და მოქმედება არის ''სასრული'', ''დისკრეტული'' და ''გარჩევადი''. ის არის პოტენციურად ულიმიტო ფირის რაოდენობა, რომელიც იძლევა უსაზღვრო [[კომპიუტერის მეხსიერება|მეხსიერებას]].
 
==ფორმალური განსაზღვრება==
 
ტიურინგისტურინგის მანქანა ფორმალურად არის განსაზღვრული 7-ნაწილისგან, <math>M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> სადაც:
 
* <math>Q</math> სასრული, არაცარიელი ''მდგომარეობების'' სიმრავლე
131 390

რედაქტირება