ეკლესია-ტურინგის თეზისი: ძირითადი ცნებები, განმარტება, გამოთვლითი ფუნქციები, მნიშვნელობა და გამოყენება

Სარჩევი:

ეკლესია-ტურინგის თეზისი: ძირითადი ცნებები, განმარტება, გამოთვლითი ფუნქციები, მნიშვნელობა და გამოყენება
ეკლესია-ტურინგის თეზისი: ძირითადი ცნებები, განმარტება, გამოთვლითი ფუნქციები, მნიშვნელობა და გამოყენება
Anonim

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

მეთოდის ეფექტურობა შედეგის მისაღწევად

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

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

ეკლესიის ნაშრომი
ეკლესიის ნაშრომი

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

  1. მეთოდი მითითებულია ზუსტი ინსტრუქციების სასრული რაოდენობის მიხედვით, თითოეული ინსტრუქცია გამოხატულია სიმბოლოების სასრული რაოდენობის გამოყენებით.
  2. იმუშავებს შეცდომების გარეშე, გამოიღებს სასურველ შედეგს გარკვეული რაოდენობის ნაბიჯებით.
  3. მეთოდი შეიძლება შეასრულოს ადამიანმა დაუხმარებლად, ქაღალდისა და ფანქრის გარდა ნებისმიერი აღჭურვილობით
  4. ეს არ საჭიროებს გაგებას, ინტუიციას ან გონიერებას მოქმედების შემსრულებლის მხრიდან

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

რეკურსიული ფუნქციების ძირითადი ცნებები

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

ეკლესია ტურინგი
ეკლესია ტურინგი

საერთო რეკურსიული ფუნქციები

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

მეთოდის შექმნაλ-კალკულუსი

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

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

რეკურსიული ფუნქციების ძირითადი ცნებები
რეკურსიული ფუნქციების ძირითადი ცნებები

ფუნქციის გამოთვლა

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

მეთოდის დასაბუთება და პრობლემები

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

რეკურსიული ფუნქციების ძირითადი ცნებები, ეკლესიის თეზისი
რეკურსიული ფუნქციების ძირითადი ცნებები, ეკლესიის თეზისი

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

რეკურსიული ფუნქციები, ეკლესიის ნაშრომი
რეკურსიული ფუნქციები, ეკლესიის ნაშრომი

თეზისი M

მნიშვნელოვანია განვასხვავოთ ტიურინგის თეზისი და მტკიცება, რომ ყველაფერი, რისი გამოთვლაც შესაძლებელია გამოთვლითი მოწყობილობის მიერ, შეიძლება გამოითვალოს მისი მანქანით. მეორე ვარიანტს აქვს თავისი განმარტება. განდი მეორე წინადადებას უწოდებს „თეზისი M“. ეს ასე გამოიყურება: „რისი გამოთვლაც შესაძლებელია მოწყობილობით, შეიძლება გამოითვალოს ტურინგის მანქანით“. თეზისის ვიწრო გაგებით, ეს არის ემპირიული წინადადება, რომლის ჭეშმარიტების მნიშვნელობა უცნობია. ტურინგის თეზისი და "თეზის M" ზოგჯერ ერთმანეთში აირია. მეორე ვერსია ზოგადად არასწორია. აღწერილია სხვადასხვა პირობითი მანქანები, რომლებსაც შეუძლიათ გამოთვალონ ფუნქციები, რომლებიც არ არის გამოთვლილი ტურინგისთვის. მნიშვნელოვანია აღინიშნოს, რომ პირველი თეზისი არ გულისხმობს მეორეს, მაგრამ შეესაბამება მის სიყალბეს.

გამოთვლითი ფუნქციები, ეკლესიის ნაშრომი
გამოთვლითი ფუნქციები, ეკლესიის ნაშრომი

თეზისის საპირისპირო მნიშვნელობა

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

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

ტურინგის მანქანა, დისერტაცია
ტურინგის მანქანა, დისერტაცია

კვანტური კომპიუტერები

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

გირჩევთ: