ახსენით კავშირი გამოთვლილ ფუნქციასა და ტურინგის მანქანის არსებობას შორის, რომელსაც შეუძლია მისი გამოთვლა.
გამოთვლითი სირთულის თეორიის სფეროში ფუნდამენტური მნიშვნელობა აქვს გამოთვლით ფუნქციასა და ტურინგის მანქანის არსებობას შორის, რომელსაც შეუძლია მისი გამოთვლა. ამ ურთიერთობის გასაგებად, ჯერ უნდა განვსაზღვროთ რა არის გამოთვლითი ფუნქცია და როგორ უკავშირდება ის ტურინგის მანქანებს.
გამოთვლითი ფუნქცია, რომელიც ასევე ცნობილია როგორც რეკურსიული ფუნქცია, არის მათემატიკური ფუნქცია, რომელიც შეიძლება გამოითვალოს ალგორითმით. ეს არის ფუნქცია, რომლისთვისაც არსებობს ტურინგის მანქანა, რომელიც, ნებისმიერი შეყვანის გათვალისწინებით, შეჩერდება და გამოიმუშავებს ამ შეყვანის სწორ გამომავალს. სხვა სიტყვებით რომ ვთქვათ, გამოთვლადი ფუნქცია არის ის, რომელიც შეიძლება ეფექტურად გამოითვალოს ტურინგის მანქანით.
ტურინგის მანქანები, თავის მხრივ, არის თეორიული გამოთვლითი მოწყობილობები, რომლებიც დაინერგა ალან ტურინგმა 1936 წელს. ისინი შედგება უჯრედებად დაყოფილი უსასრულო ლენტისაგან, წაკითხვის/ჩაწერის თავისაგან, რომელსაც შეუძლია გადაადგილება ფირზე, და მდგომარეობების ნაკრებისგან, რომლებიც მართავს. მანქანის ქცევა. მანქანა კითხულობს სიმბოლოებს ფირზე, ასრულებს გარკვეულ მოქმედებებს მისი ამჟამინდელი მდგომარეობისა და წაკითხული სიმბოლოს მიხედვით და გადადის ახალ მდგომარეობაში. ეს პროცესი გრძელდება მანამ, სანამ მანქანა არ მიაღწევს გაჩერების მდგომარეობას.
კავშირი გამოთვლილ ფუნქციასა და ტურინგის მანქანის არსებობას შორის, რომელსაც შეუძლია მისი გამოთვლა, ემყარება ტურინგ-სისრულის კონცეფციას. ამბობენ, რომ ტურინგის მანქანა არის ტურინგ-სრული, თუ მას შეუძლია ნებისმიერი სხვა ტურინგის მანქანის სიმულაცია. სხვა სიტყვებით რომ ვთქვათ, ტურინგის სრულ მანქანას შეუძლია გამოთვალოს ნებისმიერი ფუნქცია, რომელიც შეიძლება გამოითვალოს ნებისმიერი სხვა ტურინგის აპარატით.
ამ განმარტებიდან გამომდინარე, შეგვიძლია ვთქვათ, რომ თუ ფუნქცია გამოთვლადია, მაშინ არსებობს ტურინგის მანქანა, რომელსაც შეუძლია მისი გამოთვლა. პირიქით, თუ ტურინგის მანქანას შეუძლია ფუნქციის გამოთვლა, მაშინ ეს ფუნქცია გამოთვლადია. ეს ურთიერთობა ეფუძნება იმ ფაქტს, რომ ტურინგის მანქანები არის უნივერსალური გამოთვლითი მოწყობილობები, რომლებსაც შეუძლიათ ნებისმიერი სხვა ტურინგის მანქანის სიმულაცია.
ამ ურთიერთობის საილუსტრაციოდ, განვიხილოთ მაგალითი. დავუშვათ, გვაქვს გამოთვლითი ფუნქცია, რომელიც ამატებს ორ რიცხვს. ჩვენ შეგვიძლია განვსაზღვროთ ტურინგის მანქანა, რომელიც იღებს ორ შეყვანას, გადააქვს წაკითხვის/ჩაწერის თავი ფირზე პირველ რიცხვზე, დაამატებს მას მეორე რიცხვს და გამოსცემს შედეგს. ამ ტურინგის მანქანას შეუძლია გამოთვალოს დამატების ფუნქცია, აჩვენოს კავშირი გამოსათვლელ ფუნქციასა და ტურინგის მანქანის არსებობას შორის, რომელსაც შეუძლია მისი გამოთვლა.
კავშირი გამოთვლილ ფუნქციასა და ტურინგის მანქანის არსებობას შორის, რომელსაც შეუძლია მისი გამოთვლა, ემყარება ტურინგ-სისრულის კონცეფციას. გამოთვლადი ფუნქცია არის ის, რომლის ეფექტური გამოთვლა შესაძლებელია ტურინგის მანქანის მიერ, ხოლო ტურინგის მანქანა არის ტურინგის სრული, თუ მას შეუძლია ნებისმიერი სხვა ტურინგის მანქანის სიმულაცია. ამიტომ, თუ ფუნქცია გამოთვლადია, არსებობს ტურინგის მანქანა, რომელსაც შეუძლია მისი გამოთვლა და პირიქით.
სხვა ბოლოდროინდელი კითხვები და პასუხები გამოთვლადი ფუნქციები:
- რას ნიშნავს ტურინგის მანქანების სხვადასხვა ვარიაციები გამოთვლით შესაძლებლობებში ექვივალენტური იყოს?
- რა მნიშვნელობა აქვს ტურინგის მანქანას, რომელიც ყოველთვის ჩერდება გამოთვლითი ფუნქციის გამოთვლისას?
- შეიძლება თუ არა ტურინგის მანქანის შეცვლა ისე, რომ ყოველთვის მიიღოს ფუნქცია? ახსენით რატომ ან რატომ არა.
- როგორ ითვლის ტურინგის მანქანა ფუნქციას და რა როლი აქვს შემავალი და გამომავალი ლენტები?
- რა არის გამოთვლითი ფუნქცია გამოთვლითი სირთულის თეორიის კონტექსტში და როგორ განისაზღვრება იგი?