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

ისტორიის ინტერაქციულად გადახედვა

[შეუმოწმებელი ვერსია]

← წინა ცვლილება შემდეგი ცვლილება →

შიგთავსი ამოიშალა შიგთავსი დაემატა

ვიზუალურივიკიტექსტი

შიდახაზური

05:48, 5 ივნისი 2014-ის ვერსია

ტიურინგის მანქანა — ჰიპოთეტური მექანიზმი, რომელიც მანიპულირებას უკეთებს სიმბოლოოებს ფირზე, შესაბამისი ცხრილის წესების გამოყენებით. მიუხედავად მისი სიმარტივისა, ტიურინგის მანქანას შეუძლია ნებისმიერი კომპიუტერული ალგორითმის ლოგიკის სიმულაცია და ის განსაკუთრებით გამოიყენება პროცესორის ფუნქციების გასამარტად.

„ტიურინგის“ მანქანა გამოიგონა ალან ტიურინგმა 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") ტიურინგი იგონებს არა მექანიზმს, არამედ ადამიანს, რომელსაც კომპიუტერს არქმევს და რომელიც ასრულებს ამ დეტერმინისტულ ქმედებებს მონურად.

უფრო დაწვრილებით, ტიურინგის მანქანა შედგება:

ფირით, რომელიც დაყოფილია უჯრებად ერთი-მეორის მიყოლებით. ყოველი უჯრა შეიცავს სიმბოლოს სასრული ანბანიდან. ანბანი შეიცავს პეციალურ ცარიელ სიმბოლოს (ამ შემთხვევაში წერია როგორც ‘0’) და ერთი-ორ სხვა სიმბოლოს. უჯრები რომელშიც არაფერია არ წერია, ვუშვებთ რომ შეიცვას ცარიელ სიმბოლოს.
თავი, რომელიც კითხულობს ან წერს სიმბოლოებს და შემდეგ ფირი გადაადგილდება მარჯვნივ ან მარცხნივ (მხოლოდ ერთი უჯრით). ზოგი მოდელის შემთხვევაში თავი გადაადგილდება და ფირი უძრავია.
მდგომარეობის შემნახველი, რომელიც ინახავს ტიურინგის მანქანის მდგომარეობას. ფირზე არის ერთი სპეციალური საწყისი მდგომარეობა, სადაც ტიურინგის მანქანა ინიციალიზირდება.
სასრული ცხრილი (ხშირად მოიხსენიება, როგორც მოქმედების ცხრილი ან გარდამავალი ფუნქცია). მაგალითად, მოცემულია მდგომარეობა(q_i), სადაც მანქანა არის და კითხულობს სიმბოლოს(a_j) , რომელიც ეუბნება შემდეგს:
- წაშალოს ან ჩაწეროს სიმბოლო (შეცვალოს a_j a_j1-ით), შემდეგ
- შეიცვალოს მდგომარეობა (გადაადგილდეს მარჯვნიც ან მარცხნივ)

მნიშვნელოვანია ის ფაქტი, რომ ტიურინგის მანქანის ყველა ნაწილი და მოქმედება არის სასრული, დისკრეტული და გარჩევადი. ის არის პოტენციურად ულიმიტო ფირის რაოდენობა, რომელიც იძლევა უსაზღვრო მეხსიერებას.

ფორმალური განსაზღვრება

ტიურინგის მანქანა ფორმალურად არის განსაზღვრული 7-ნაწილისგან, $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ სადაც:

$Q$ სასრული, არაცარიელი მდგომარეობების სიმრავლე
$\Gamma$ სასრული, არაცარიელი ფირის ანბანის/სიმბოლოების სიმრავლე
$b\in \Gamma$ ცარიელი სიმბოლო
$\Sigma \subseteq \Gamma \setminus \{b\}$ შემომავალი სიმბოლოების სიმრავლე
$q_{0}\in Q$ საწყისი მდგომარეობა
$F\subseteq Q$ საბოლოო მდგომარეობების სიმრავლე
$\delta :Q\setminus F\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ გარდამავალი ფუნქცია, სადაც L არის მარცხენა გადაადგილება, R-კი მარჯვენა.

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