გამოთვლითი სირთულის თეორიის სფეროში გადაწყვეტილების ცნება ფუნდამენტურ როლს ასრულებს. ენა შეიძლება გადაწყდეს, თუ არსებობს ტურინგის მანქანა (TM), რომელსაც შეუძლია განსაზღვროს ნებისმიერი მოცემული შეყვანისთვის, ეკუთვნის თუ არა ენას. ენის გადაწყვეტადობა მნიშვნელოვანი თვისებაა, რადგან ის საშუალებას გვაძლევს ვიმსჯელოთ ენისა და მისი თვისებების შესახებ ალგორითმულად.
ტურინგის მანქანების ეკვივალენტობის კითხვა ეხება იმის დადგენას, აღიარებს თუ არა ორი მოცემული TM ერთსა და იმავე ენას. ფორმალურად, ორი TM M1 და M2 მოცემული, ეკვივალენტობის კითხვა სვამს თუ არა L(M1) = L(M2), სადაც L(M) წარმოადგენს TM M-ის მიერ აღიარებულ ენას.
ცნობილია, რომ ორი TM-ის ეკვივალენტობის განსაზღვრის ზოგადი პრობლემა გადაუწყვეტელია. ეს ნიშნავს, რომ არ არსებობს ალგორითმი, რომელსაც ყოველთვის შეუძლია გადაწყვიტოს ორი თვითნებური TM აღიარებს თუ არა ერთსა და იმავე ენას. ეს შედეგი დაამტკიცა ალან ტურინგმა გამოთვლების შესახებ თავის მთავარ ნაშრომში.
თუმცა, მნიშვნელოვანია აღინიშნოს, რომ ეს შედეგი ეხება თვითნებური TM-ების ზოგად შემთხვევას. კონკრეტულ შემთხვევაში, როდესაც ორივე TM აღწერს გადაწყვეტილ ენებს, ეკვივალენტობის საკითხი გადაწყვეტად ხდება. ეს იმიტომ ხდება, რომ გადაწყვეტადი ენები არის ის ენები, რომლებისთვისაც არსებობს TM, რომელსაც შეუძლია გადაწყვიტოს ენის წევრობა. ამიტომ, თუ ორი TM აღწერს გადაწყვეტილ ენებს, ჩვენ შეგვიძლია ავაშენოთ ახალი TM, რომელიც განსაზღვრავს მათ ეკვივალენტობას.
ამის საილუსტრაციოდ, განვიხილოთ მაგალითი. დავუშვათ, გვაქვს ორი TM M1 და M2, რომლებიც აღწერს გადაწყვეტილ ენებს. ჩვენ შეგვიძლია ავაშენოთ ახალი TM M, რომელიც გადაწყვეტს მათ ეკვივალენტობას შემდეგნაირად:
1. x შეყვანის მიცემით, M1 სიმულაცია x-ზე და M2 x-ზე ერთდროულად.
2. თუ M1 იღებს x-ს და M2 იღებს x-ს, მაშინ მიიღეთ.
3. თუ M1 უარყოფს x-ს და M2 უარყოფს x-ს, მაშინ მიიღე.
4. წინააღმდეგ შემთხვევაში, უარი.
კონსტრუქციით, TM M მიიღებს x შეყვანას, თუ და მხოლოდ იმ შემთხვევაში, თუ M1 და M2 მიიღებენ x-ს, ან ორივე M1 და M2 უარყოფენ x-ს. ეს ნიშნავს, რომ M წყვეტს M1-ისა და M2-ის ეკვივალენტობას ნებისმიერი მოცემული x შეყვანისთვის.
მიუხედავად იმისა, რომ ორი თვითნებური TM-ის ეკვივალენტობის განსაზღვრის ზოგადი პრობლემა გადაუწყვეტელია, თუ TM-ები აღწერს გადაწყვეტად ენებს, ეკვივალენტობის საკითხი გადასაწყვეტი ხდება. ეს იმიტომ ხდება, რომ გადაწყვეტადი ენები შეიძლება გადაწყდეს TM-ით, რაც საშუალებას გვაძლევს ავაგოთ TM, რომელიც განსაზღვრავს მათ ეკვივალენტობას. ეკვივალენტობის საკითხის გადაწყვეტადობა TM-ებისთვის, რომლებიც აღწერს გადაწყვეტად ენებს, იძლევა მნიშვნელოვან ინფორმაციას ამ ენების გამოთვლითი სირთულის შესახებ.
სხვა ბოლოდროინდელი კითხვები და პასუხები გადაწყვეტილების მიღება:
- შეიძლება თუ არა ლენტი შემოიფარგლოს შეყვანის ზომით (რაც ექვივალენტურია ტურინგის მანქანის ხელმძღვანელის შეზღუდული TM ფირის შეყვანის მიღმა გადაადგილებით)?
- რას ნიშნავს ტურინგის მანქანების სხვადასხვა ვარიაციები გამოთვლით შესაძლებლობებში ექვივალენტური იყოს?
- შეუძლია თუ არა ტურინგის ცნობადმა ენამ შექმნას გადამწყვეტი ენის ქვეჯგუფი?
- გადასაწყვეტია თუ არა ტურინგის მანქანის გაჩერების პრობლემა?
- რით განსხვავდება წრფივი შეზღუდული ავტომატების მიღების პრობლემა ტურინგის მანქანებისგან?
- მოიყვანეთ პრობლემის მაგალითი, რომელიც შეიძლება გადაწყდეს წრფივი შემოსაზღვრული ავტომატით.
- განმარტეთ გადაწყვეტილების ცნება ხაზოვანი შეზღუდული ავტომატების კონტექსტში.
- როგორ მოქმედებს ფირის ზომა ხაზოვანი შეზღუდულ ავტომატებში განსხვავებული კონფიგურაციების რაოდენობაზე?
- რა არის მთავარი განსხვავება წრფივი შეზღუდულ ავტომატებსა და ტურინგის მანქანებს შორის?
- აღწერეთ ტურინგის მანქანის გარდაქმნის პროცესი PCP-სთვის ფილების ნაკრებად და როგორ წარმოადგენენ ეს ფილები გამოთვლის ისტორიას.
იხილეთ მეტი კითხვა და პასუხი Decidability-ში