Church-Turing Thesis
চার্চ-টুরিং থিসিস
দাবি — 'effectively computable' (algorithm দিয়ে গণনাযোগ্য) প্রতিটা function ঠিক ততগুলোই যতগুলো Turing machine দিয়ে গণনাযোগ্য। প্রমাণযোগ্য নয় (empirical claim), কিন্তু একাধিক স্বাধীন মডেলের একত্রীকরণ এর পক্ষে শক্তিশালী প্রমাণ।
also: Church-Turing, CT thesis
Theorem না, thesis — কারণ “effectively computable”-এর কোনো স্বাধীন আনুষ্ঠানিক সংজ্ঞা নেই যার বিরুদ্ধে Turing machine-কে গাণিতিকভাবে “সমান” প্রমাণ করা যায়।
পক্ষের যুক্তি তিন স্তম্ভে: (১) Turing machine, lambda calculus, general recursive functions — সম্পূর্ণ ভিন্ন গঠনের তিনটা স্বাধীনভাবে আবিষ্কৃত মডেল, সবাই একই function-এর সেটে গিয়ে মেলে; (২) ৯০ বছরে কোনো পাল্টা উদাহরণ নেই; (৩) Turing-এর নিজের বিশ্লেষণী যুক্তি — মানুষের গণনা প্রক্রিয়ার সীমাবদ্ধতা থেকে সরাসরি TM-এর সংজ্ঞায় পৌঁছানো।
Physical Church-Turing thesis — একটা শক্তিশালী সংস্করণ, দাবি করে মহাবিশ্বের যেকোনো ভৌত প্রক্রিয়া TM দিয়ে simulate করা যায়। Quantum computer এটা লঙ্ঘন করে না — এটা computability না, শুধু complexity বদলায় (একই ফলাফল, ভিন্ন গতি)।