ენას უწოდებენ გადაწყვეტადს ან რეკურსიულს, თუ არის ტურინგის მანქანა, რომელიც იღებს და ჩერდება ყველა შეყვანის სტრიქონზე w. ყველა გადასაწყვეტი ენა ტურინგისთვის მისაღებია. გადაწყვეტილების პრობლემა P არის გადაწყვეტილი, თუ P-ის ყველა დიახ ინსტანციის L ენა გადაწყვეტადია.
რას გულისხმობთ გადაწყვეტილების მიღებაში?
: შეიძლება კონკრეტულად გადაწყვეტილების მიღება: შეიძლება გადაწყვიტოს, როგორც ლოგიკური სისტემის აქსიომებიდან გამომდინარე, თუ არა, იყო თუ არა ლოგიკა სრული…? და გადასაწყვეტი იყო თუ არა იმ გაგებით, რომ არსებობდა მეთოდი, რომელიც აჩვენებდა ყველა განცხადების სიმართლეს ან სიცრუეს? -
რა განსხვავებაა გადაწყვეტადობასა და გადაუჭრელობას შორის?
გადაწყვეტილების პრობლემა გადაწყვეტილია, თუ არსებობს მისთვის გადაწყვეტილების ალგორითმი. წინააღმდეგ შემთხვევაში გადაუწყვეტელია. იმის საჩვენებლად, რომ გადაწყვეტილების პრობლემა გადაწყვეტადია, საკმარისია მისცეს ალგორითმი.
როგორ ითვლით გადაწყვეტილების მიღებას?
ენა არის გადაწყვეტა, თუ და მხოლოდ იმ შემთხვევაში, თუ ის და მისი დანამატი ამოსაცნობია. მტკიცებულება. თუ ენა გადაწყვეტადია, მაშინ მისი კომპლიმენტი გადასაწყვეტია (დახურვით შევსებისას).
რა არის გადაწყვეტილების პრობლემა?
(განსაზღვრება) განმარტება: გადაწყვეტილების პრობლემა, რომელიც შეიძლება გადაიჭრას ალგორითმით, რომელიც ჩერდება ყველა შეყვანაზე სასრული რაოდენობის ნაბიჯებით ასოცირებულ ენას ეწოდება გადაწყვეტადი ენა. ასევე ცნობილია, როგორც სრულიად გადასაწყვეტი პრობლემა, ალგორითმულად ამოსახსნელი, რეკურსიულად ამოსახსნელი.
