চার্চ-টুরিং থিসিস যুক্তিবিদ্যা, গণিত এবং কম্পিউটার বিজ্ঞানে একটি দক্ষ, পদ্ধতিগত, বা যান্ত্রিক পদ্ধতির ধারণাকে বোঝায়। এটি গণনাযোগ্যতার স্বজ্ঞাত ধারণার বর্ণনা হিসাবে প্রণয়ন করা হয় এবং সাধারণ পুনরাবৃত্ত ফাংশনগুলির সাথে সম্পর্কিত, এটিকে প্রায়শই চার্চের থিসিস বলা হয়। এটি কম্পিউটার-কম্পিউটেবল ফাংশনের তত্ত্বকেও বোঝায়। থিসিসটি 1930-এর দশকে উপস্থিত হয়েছিল, যখন কম্পিউটারগুলি এখনও বিদ্যমান ছিল না। পরবর্তীতে আমেরিকান গণিতবিদ আলোনসো চার্চ এবং তার ব্রিটিশ সহকর্মী অ্যালান টুরিংয়ের নামে এর নামকরণ করা হয়।
ফলাফল অর্জনের পদ্ধতির কার্যকারিতা
একটি আধুনিক কম্পিউটারের অনুরূপ প্রথম ডিভাইসটি ছিল বোম্বি, ইংরেজ গণিতবিদ অ্যালান টুরিং দ্বারা তৈরি একটি মেশিন। এটি দ্বিতীয় বিশ্বযুদ্ধের সময় জার্মান বার্তা পাঠোদ্ধার করতে ব্যবহৃত হয়েছিল। কিন্তু তার থিসিস এবং একটি অ্যালগরিদমের ধারণার আনুষ্ঠানিককরণের জন্য, তিনি বিমূর্ত মেশিন ব্যবহার করেন, যা পরে টুরিং মেশিন নামে পরিচিত। থিসিস উপস্থাপনগণিতবিদ এবং প্রোগ্রামার উভয়ের জন্যই আগ্রহ, যেহেতু এই ধারণাটি প্রথম কম্পিউটারের নির্মাতাদের অনুপ্রাণিত করেছিল।
গণনীয়তা তত্ত্বে, চার্চ-টুরিং থিসিস গণনাযোগ্য ফাংশনের প্রকৃতি সম্পর্কে অনুমান হিসাবেও পরিচিত। এটি বলে যে প্রাকৃতিক সংখ্যার উপর যেকোন অ্যালগরিদমিকভাবে গণনাযোগ্য ফাংশনের জন্য, এটি গণনা করতে সক্ষম একটি টিউরিং মেশিন রয়েছে। অথবা, অন্য কথায়, এটির জন্য উপযুক্ত একটি অ্যালগরিদম আছে। এই পদ্ধতির কার্যকারিতার একটি সুপরিচিত উদাহরণ হল টাউটোলজি পরীক্ষার জন্য সত্য সারণী পরীক্ষা৷
যেকোন পছন্দসই ফলাফল অর্জনের একটি উপায়কে বলা হয় "কার্যকর", "পদ্ধতিগত" বা "যান্ত্রিক" যদি:
- পদ্ধতিটি নির্দিষ্ট সংখ্যক সঠিক নির্দেশের পরিপ্রেক্ষিতে নির্দিষ্ট করা হয়েছে, প্রতিটি নির্দেশকে একটি সীমিত সংখ্যক অক্ষর ব্যবহার করে প্রকাশ করা হয়েছে।
- এটি ত্রুটি ছাড়াই চলবে, নির্দিষ্ট সংখ্যক ধাপে কাঙ্খিত ফলাফল দেবে।
- এই পদ্ধতিটি কাগজ এবং পেন্সিল ব্যতীত অন্য যে কোনও সরঞ্জামের সাহায্যে বিনা সহায়তায় একজন মানুষের দ্বারা সঞ্চালিত হতে পারে
- যার জন্য ক্রিয়া সম্পাদনকারী ব্যক্তির পক্ষ থেকে বোঝার, অন্তর্দৃষ্টি বা চতুরতার প্রয়োজন হয় না
গণিতের আগে, অনানুষ্ঠানিক শব্দটি "কার্যকরভাবে গণনাযোগ্য" ফাংশনগুলি বোঝাতে ব্যবহৃত হত যা পেন্সিল এবং কাগজ দিয়ে গণনা করা যেতে পারে। কিন্তু অ্যালগরিদমিক কম্পিউটিবিলিটির ধারণাটি কংক্রিটের চেয়ে বেশি স্বজ্ঞাত ছিল। এখন এটি একটি প্রাকৃতিক যুক্তি সহ একটি ফাংশন দ্বারা চিহ্নিত করা হয়েছিল, যার জন্য একটি গণনা অ্যালগরিদম রয়েছে। অ্যালান টুরিং-এর অন্যতম কৃতিত্ব ছিলএকটি আনুষ্ঠানিকভাবে সঠিক ভবিষ্যদ্বাণীর উপস্থাপনা, যার সাহায্যে পদ্ধতির দক্ষতার শর্তটি ব্যবহার করা হলে অনানুষ্ঠানিকটিকে প্রতিস্থাপন করা সম্ভব হবে। চার্চ একই আবিষ্কার করেছে।
পুনরাবৃত্ত ফাংশনের মৌলিক ধারণা
টুরিংয়ের ভবিষ্যদ্বাণীর পরিবর্তন, প্রথম নজরে, তার সহকর্মীর প্রস্তাবিত থেকে আলাদা লাগছিল। কিন্তু ফলস্বরূপ, তারা সমতুল্য হয়ে উঠেছে, এই অর্থে যে তাদের প্রত্যেকে গাণিতিক ফাংশনের একই সেট নির্বাচন করে। চার্চ-টুরিং থিসিস হল এই দাবি যে এই সেটটিতে প্রতিটি ফাংশন রয়েছে যার মানগুলি এমন একটি পদ্ধতি দ্বারা প্রাপ্ত করা যেতে পারে যা দক্ষতার শর্তগুলিকে সন্তুষ্ট করে। দুটি আবিষ্কারের মধ্যে আরেকটি পার্থক্য ছিল। এটি ছিল চার্চ শুধুমাত্র ধনাত্মক পূর্ণসংখ্যার উদাহরণ হিসাবে বিবেচনা করেছিল, যখন টুরিং তার কাজকে একটি অখণ্ড বা বাস্তব পরিবর্তনশীল দিয়ে গণনাযোগ্য ফাংশনগুলিকে আচ্ছাদন হিসাবে বর্ণনা করেছিলেন৷
সাধারণ পুনরাবৃত্ত ফাংশন
চার্চের মূল সূত্রে বলা হয়েছে যে গণনাটি λ-ক্যালকুলাস ব্যবহার করে করা যেতে পারে। এটি জেনেরিক রিকারসিভ ফাংশন ব্যবহার করার সমতুল্য। চার্চ-টুরিং থিসিসটি মূলত ধারণার চেয়ে বেশি ধরণের গণনা কভার করে। উদাহরণস্বরূপ, সেলুলার অটোমেটা, কম্বিনেটর, রেজিস্ট্রেশন মেশিন এবং প্রতিস্থাপন সিস্টেম সম্পর্কিত। 1933 সালে, গণিতবিদ কার্ট গোডেল এবং জ্যাক হারব্র্যান্ড সাধারণ পুনরাবৃত্ত ফাংশন নামে একটি শ্রেণীর একটি আনুষ্ঠানিক সংজ্ঞা তৈরি করেছিলেন। এটি এমন ফাংশন ব্যবহার করে যেখানে একাধিক আর্গুমেন্ট সম্ভব।
একটি পদ্ধতি তৈরি করা হচ্ছেλ-ক্যালকুলাস
1936 সালে, আলোনসো চার্চ λ-ক্যালকুলাস নামে একটি নির্ণয়ের পদ্ধতি তৈরি করে। তিনি প্রাকৃতিক সংখ্যার সাথে যুক্ত ছিলেন। λ-ক্যালকুলাসের মধ্যে, বিজ্ঞানী তাদের এনকোডিং নির্ধারণ করেছিলেন। ফলস্বরূপ, তাদের চার্চ সংখ্যা বলা হয়। প্রাকৃতিক সংখ্যার উপর ভিত্তি করে একটি ফাংশনকে λ-কম্পিউটেবল বলা হত। আরেকটি সংজ্ঞা ছিল। চার্চের থিসিস থেকে ফাংশনকে দুটি শর্তে λ-কম্পিউটেবল বলা হয়। প্রথমটি এইরকম শোনাচ্ছিল: যদি এটি চার্চের উপাদানগুলির উপর গণনা করা হয়, এবং দ্বিতীয় শর্তটি ছিল λ-ক্যালকুলাসের সদস্য দ্বারা প্রতিনিধিত্ব করার সম্ভাবনা।
এছাড়াও 1936 সালে, তার সহকর্মীর কাজ অধ্যয়ন করার আগে, টুরিং বিমূর্ত মেশিনগুলির জন্য একটি তাত্ত্বিক মডেল তৈরি করেছিলেন যা এখন তার নামে নামকরণ করা হয়েছে। তারা টেপের অক্ষরগুলিকে হেরফের করে গণনা করতে পারে। এটি তাত্ত্বিক কম্পিউটার বিজ্ঞানে পাওয়া অন্যান্য গাণিতিক ক্রিয়াকলাপের ক্ষেত্রেও প্রযোজ্য, যেমন কোয়ান্টাম সম্ভাব্য কম্পিউটিং। চার্চের থিসিস থেকে ফাংশনটি শুধুমাত্র পরে একটি টুরিং মেশিন ব্যবহার করে প্রমাণিত হয়েছিল। প্রাথমিকভাবে, তারা λ-ক্যালকুলাসের উপর নির্ভর করত।
ফাংশন গণনাযোগ্যতা
যখন প্রাকৃতিক সংখ্যাগুলি যথাযথভাবে অক্ষর ক্রম হিসাবে এনকোড করা হয়, তখন প্রাকৃতিক সংখ্যার একটি ফাংশনকে টিউরিং-কম্পিউটেবল বলা হয় যদি বিমূর্ত মেশিনটি প্রয়োজনীয় অ্যালগরিদম খুঁজে পায় এবং এই ফাংশনটি টেপে মুদ্রণ করে। এই জাতীয় ডিভাইস, যা 1930-এর দশকে বিদ্যমান ছিল না, ভবিষ্যতে একটি কম্পিউটার হিসাবে বিবেচিত হবে। বিমূর্ত টুরিং মেশিন এবং চার্চের থিসিস উন্নয়নের একটি যুগের সূচনা করেছেকম্পিউটিং ডিভাইস. এটি প্রমাণিত হয়েছিল যে উভয় বিজ্ঞানীদের দ্বারা আনুষ্ঠানিকভাবে সংজ্ঞায়িত ফাংশনের শ্রেণীগুলি মিলে যায়। অতএব, ফলস্বরূপ, উভয় বিবৃতি একত্রিত হয়েছিল। কম্পিউটেশনাল ফাংশন এবং চার্চের থিসিসও গণনাযোগ্যতার ধারণার উপর একটি শক্তিশালী প্রভাব ফেলেছিল। তারা গাণিতিক যুক্তি এবং প্রমাণ তত্ত্বের জন্য একটি গুরুত্বপূর্ণ হাতিয়ার হয়ে উঠেছে৷
পদ্ধতির যৌক্তিকতা এবং সমস্যা
থিসিসটিতে পরস্পরবিরোধী মতামত রয়েছে। 1936 সালে চার্চ এবং টুরিং দ্বারা প্রস্তাবিত "কার্যকর অনুমান" এর জন্য অসংখ্য প্রমাণ সংগ্রহ করা হয়েছিল। কিন্তু প্রদত্তগুলি থেকে নতুন কার্যকরীভাবে গণনাযোগ্য ফাংশন আবিষ্কারের জন্য সমস্ত পরিচিত পদ্ধতি বা অপারেশনগুলি মেশিন নির্মাণের পদ্ধতিগুলির সাথে সংযুক্ত ছিল, যা তখন বিদ্যমান ছিল না। চার্চ-টুরিং থিসিস প্রমাণ করার জন্য, একজন এই সত্য থেকে শুরু করে যে গণনার প্রতিটি বাস্তবসম্মত মডেল সমতুল্য।
বিভিন্ন বিশ্লেষণের কারণে, এটি সাধারণত বিশেষ শক্তিশালী প্রমাণ হিসাবে বিবেচিত হয়। একটি কার্যকরীভাবে গণনাযোগ্য ফাংশনের স্বজ্ঞাত ধারণাটিকে আরও সুনির্দিষ্টভাবে সংজ্ঞায়িত করার সমস্ত প্রচেষ্টা সমতুল্য হয়ে উঠেছে। প্রস্তাবিত প্রতিটি বিশ্লেষণে প্রমাণিত হয়েছে যে একই শ্রেণীর ফাংশনগুলিকে আলাদা করা হয়েছে, যেমন যেগুলি টুরিং মেশিন দ্বারা গণনা করা যায়। কিন্তু কিছু কম্পিউটেশনাল মডেল বিভিন্ন কাজের জন্য সময় এবং মেমরি ব্যবহারের ক্ষেত্রে আরও দক্ষ বলে প্রমাণিত হয়েছে। পরে এটি লক্ষ করা গেছে যে পুনরাবৃত্ত ফাংশন এবং চার্চের থিসিসগুলির মৌলিক ধারণাগুলি বরং অনুমানমূলক৷
থিসিস এম
টুরিংয়ের থিসিস এবং এই দাবির মধ্যে পার্থক্য করা গুরুত্বপূর্ণ যে একটি কম্পিউটিং ডিভাইস দ্বারা যা কিছু গণনা করা যায় তার মেশিন দ্বারা গণনা করা যেতে পারে। দ্বিতীয় বিকল্পটির নিজস্ব সংজ্ঞা রয়েছে। গান্ধী দ্বিতীয় বাক্যটিকে "থিসিস এম" বলেছেন। এটি এভাবে যায়: "একটি ডিভাইস দ্বারা যা কিছু গণনা করা যায় তা একটি টুরিং মেশিন দ্বারা গণনা করা যেতে পারে।" থিসিসের সংকীর্ণ অর্থে, এটি একটি অভিজ্ঞতামূলক প্রস্তাব যার সত্য মূল্য অজানা। টুরিং এর থিসিস এবং "থিসিস এম" মাঝে মাঝে বিভ্রান্ত হয়। দ্বিতীয় সংস্করণটি ব্যাপকভাবে ভুল। বিভিন্ন শর্তসাপেক্ষ মেশিন বর্ণনা করা হয়েছে যেগুলি এমন ফাংশনগুলি গণনা করতে পারে যা টুরিং গণনাযোগ্য নয়। এটি লক্ষ করা গুরুত্বপূর্ণ যে প্রথম থিসিসটি দ্বিতীয়টির সাথে জড়িত নয়, তবে এটির মিথ্যার সাথে সামঞ্জস্যপূর্ণ৷
থিসিসের বিপরীত প্রভাব
কম্পিউটিবিলিটি তত্ত্বে, চার্চের থিসিসটি সাধারণ পুনরাবৃত্ত ফাংশনগুলির একটি শ্রেণীর দ্বারা গণনাযোগ্যতার ধারণার বর্ণনা হিসাবে ব্যবহৃত হয়। আমেরিকান স্টিফেন ক্লিন আরও সাধারণ সূত্র দিয়েছেন। তিনি আংশিকভাবে পুনরাবৃত্ত সমস্ত আংশিক ফাংশনকে অ্যালগরিদম দ্বারা গণনাযোগ্য বলেছেন৷
রিভার্স ইমপ্লিকেশনকে সাধারণত চার্চের বিপরীত থিসিস বলা হয়। এটি সত্য যে ধনাত্মক পূর্ণসংখ্যার প্রতিটি পুনরাবৃত্তিমূলক ফাংশন দক্ষতার সাথে মূল্যায়ন করা হয়। একটি সংকীর্ণ অর্থে, একটি থিসিস কেবল এমন একটি সম্ভাবনাকে বোঝায়। এবং একটি বৃহত্তর অর্থে, এটি এই শর্তযুক্ত মেশিনটি এতে বিদ্যমান আছে কিনা সেই প্রশ্ন থেকে বিমূর্ত হয়৷
কোয়ান্টাম কম্পিউটার
কম্পিউটেবল ফাংশনের ধারণা এবং চার্চের থিসিস গণিত, মেশিন তত্ত্ব এবং অন্যান্য অনেক বিজ্ঞানের জন্য একটি গুরুত্বপূর্ণ আবিষ্কার হয়ে উঠেছে। কিন্তু প্রযুক্তি অনেক পরিবর্তিত হয়েছে এবং উন্নতি অব্যাহত। ধারণা করা হয় যে কোয়ান্টাম কম্পিউটার আধুনিক কম্পিউটারের তুলনায় কম সময়ে অনেক সাধারণ কাজ সম্পাদন করতে পারে। কিন্তু প্রশ্ন থেকে যায়, যেমন থামার সমস্যা। একটি কোয়ান্টাম কম্পিউটার এর উত্তর দিতে পারে না। এবং, চার্চ-টুরিং থিসিস অনুসারে, অন্য কোন কম্পিউটিং ডিভাইসও নেই।
